Algorithm Complexity and Big O Notation

Hello students, welcome to Kwickprep. Two programs give the same answer, but one takes a second and the other takes an hour. How do we compare them without a stopwatch? Today we learn complexity and Big O notation.

An algorithm is a step by step method to solve a problem. Many algorithms can solve the same problem, so we need a fair way to choose. A stopwatch is not fair, because a fast laptop beats an old computer. So we count the number of basic steps as the input size grows, and we call that size n. Time complexity counts steps, and space complexity counts the extra memory used.

Here is why it matters. Think of finding one roll number in a list of n students. For ten students, checking each one takes ten steps, while halving the sorted list takes about four. For one thousand students, it is one thousand steps against about ten. For ten lakh students, it is ten lakh steps against about twenty. The difference grows huge as n grows.

Big O notation is a short way to write this growth. It gives the order of growth, meaning the shape of the step count, not the exact number. It tells us how the steps grow when n becomes very large. It is usually used for the worst case, which is the slowest possible input. We write capital O with n in brackets, and we read it as order n.

To find Big O, we keep only the dominant term. The dominant term is the part that grows fastest as n grows. In three n plus five, the three n term wins, so it is order n. In two n squared plus seven n plus four, n squared wins, so it is order n squared. In five n cubed plus one hundred n squared, it is order n cubed. A fixed count like fifty steps is order one, called constant time.

Let us check why the small terms can be dropped. When n is ten, two n squared is two hundred, and seven n plus four is seventy four. When n is one thousand, it is twenty lakh against about seven thousand. When n is one lakh, two n squared is two thousand crore, against about seven lakh. The small terms hardly matter, and constants like two are dropped too.

Here are the orders you must know, from fastest to slowest. Order one is constant, like reading the first element of an array. Order log n is logarithmic, like binary search, which halves the list each time. Order n is linear, like linear search. Order n log n is seen in merge sort. Order n squared is quadratic, like bubble sort.

Now let us read Big O straight from loops. This loop adds every element of an array a. The loop body runs once for each i from zero to n minus one, so it runs n times. The line sum equals zero runs once. That gives n plus one steps, and the dominant term makes it order n.

Here one loop is inside another. For each value of i, the inner loop runs n times. The outer loop runs n times, so c plus plus runs n into n times. That is order n squared. Pause and predict. If n doubles, how many more steps? Four times as many, because two squared is four.

In this loop, i is divided by two each time. Starting at sixteen, i becomes eight, four, two, and then stops. That is only four steps for sixteen. The number of halvings is log to base two of n, so it is order log n.

Let us collect the loop rules. A loop that adds one to i until n is order n. Two separate loops, one after the other, give n plus n, which is still order n. A loop inside a loop multiplies, giving order n squared. A loop that doubles or halves i is order log n. Code with no loop on n is order one.

The same algorithm can take different steps for different inputs of the same size. The best case is the input that needs the fewest steps. The worst case is the input that needs the most steps. The average case is the expected number of steps over all possible inputs. Exams mostly ask the worst case, because it is a guarantee that the program will never be slower.

Let us apply this to searching and sorting. In linear search, if the item is first, it takes one step, but if it is last or missing, it takes n steps. Its average is also order n, about n by two checks. Binary search is best when the middle item matches, and worst is order log n. Simple bubble sort always runs both loops, so it is order n squared in every case.

Let us revise. Complexity counts steps as the input size n grows, not seconds on a clock. For Big O, keep the dominant term and drop the constants. One loop is order n, nested loops are order n squared, and halving loops are order log n. Every algorithm has a best, average and worst case. Big O usually reports the worst case. Practise by finding the Big O of every loop in your textbook.