Time Complexity

This is a beginners course of C programming language and not a CS 101 course, but we still need to talk a little bit about the time complexity of a program, just because, first, it's fun, and second, it's an important concept you need to be aware when you write your code.

Number of operations

Without going too deep, we can state that the computer performs some operations, such as arithmetic operations, or copying the data between memory and CPU, and the idea of talking about the time complexity is to get an idea of how many operations does the computer perform for this or that code, depending on the size of the input.

We are not going to calculate the exact number (some serious books like Knuth do that, if you're interested), but we already know enough to do some reasonable estimations. The notation we will use is the so called "big O" notation, which comes directly from calculus (where, together with "little o" notation, it is used for estimating how functions relate to each other). But let's start with the simple example first.

Constant time

If your code is linear–that is, it has no loops or function calls–it is pretty safe to say that the computer will perform some constant number of operations when it executes this code. Look at the code that swaps the values of two variables using the third variable as a temporary storage:

int a = 5, b = 7, c;

c = a;
a = b;
b = c;

We don't know exactly how much time the computer will spend on executing this code (not much!), but it's always the same number of actions it will do, regardless of the values of these variables: it's as fast to swap 5 and 7 as it is to swap 5000000 and 7000000.

We say that this code has constant time complexity.

Linear time

Now let's look at the code that calculates the sum of all elements of an array of size N:

int arr[1000], N, i;
int sum = 0;

/* ... somehow fill the array with data ... */

for (i = 0; i < N; ++i) {
  sum += arr[i];
}

In this case we can see that the number of operations the computer will perform will be different if N is 1, or if N is 1000. The body of the for loop will be executed N times, so if the computer needs t microseconds to perform one iteration, the total time it consumes will be somewhat around N × t. We don't know the exact value of t and we don't need to know it; but we do know that the time needed to execute this for loop grows linearly of N. Using the "big O" notation, we can write that the time complexity of this code is O(N), which means that one can find such a constant M that whatever the actual time is, it will be less than M × N for large values of N.

If you look at the linear search, you will notice the same pattern: the implementation is just a for loop checking all elements of the given array. It might find the element it looks for sooner than that, but in the worst case, it will check all elements. So if the array has N elements, the linear search has time complexity O(N).

Going back to the constant complexity and formally applying the big O notation to it, we can say that constant complexity is O(1).

So far in this course we haven't yet seen the code that is slower than linear (we'll see some examples soon, just not right now). But we have just wrote the code which is faster than linear (but slower than constant, of course)!

Analyzing binary search

How many operations does the binary search perform on an array of size N? Again, in the best case, the element we are looking for is in the middle and we'll find it right away, but what happens in the worst case? Let's look at this example again, we look for 4 in the given array:

index  :  0  1  2  3  4  5  6
element:  1  3  5  7  9 11 13

1st step [        mid        ]
2nd step [  mid  ]
3rd step      [mid]

So, in an array of 7 elements we need not more than 3 checks to either find a given number, or make sure it's not there.

But what if our array has 15 elements, and we want to find 4 in this array again?

index  :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
element:  1  3  5  7  9 11 15 16 17 21 22 25 26 31 44 57

1st step [                    mid                       ]
2st step [        mid        ]
3nd step [  mid  ]
4rd step      [mid]

On the first iteration we look at element #7 and go to the left half. After removing the middle element from the range, the left half has 7 elements, and we already know we only need 3 iterations for 7 elements; so for 15 elements, we need 4 iterations.

If we had N elements on start, we'll have not more than N/2 elements to check after the first iteration. After the second iteration, it's not more than N/4.

How many times can you divide N elements in half, until you have no elements left?

Here you will need just a little bit of your Algebra 1 to figure out that we are talking about the logarithm here; specifically, the base 2 logarithm. Indeed: 2³ is 8, and we don't need more than 3 steps for arrays smaller than 8 elements. We need 4 steps for arrays up to 15 elements (2⁴ = 16), and so on, which allows us to say the the time complexity of the binary search is O(log₂N), which is much faster than O(N) for large values of N.

That would be enough for the topic of complexity for now; we'll get back to writing code, and will talk more about time complexity when we have some interesting examples!