1.2 Time Complexity Explained in C

1. Time and Space Complexity in C

Full Course on Data Structures and Algorithms in C

The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Time Complexity refers to how fast a piece of code (a function for example, and not the whole program) runs from beginning to completion. Since different computers have different microprocessor clock frequencies and different sizes of memory, the same code will take different durations to run in different computers. Because of this issue and others, time complexity is given as relative speed.

Time complexity is the maximum number of main operations the piece of code needs, to solve a type of problem, in the worst case situation. There is Constant Time Complexity, Linear Time Complexity, Logarithmic Time Complexity, Quadratic Time Complexity, Exponential Time Complexity and Factorial Time Complexity.

A typical way to express time complexity, is with the Big-O notation, of which examples are given below.

Constant Time - O(1)

Consider the following function:

    void solution() {
        int result = 5 + 5;
        printf("%i\n", result);
    }

There are two statements in the body of the function, solution(). After compilation, these statements are in binary code, of more than two lines, but still not of many lines. These two statements are executed in a short time. This is known as constant time, written in Big-O notation as O(1), where the 1 in parentheses means, short duration or constant time. The exact time in milliseconds (seconds), is not emphasized upon, in the topic, time complexity. Constant time operation is best considered as one main operation.

Linear Time - O(n)

The above two statements can be considered as the main operation for the above function code. Consider the following function:

    void solution() {
        int N = 8;
        for (int i=0; i<N; i++) {
            printf("%i ", i);
        }
        printf("\n");
    }

The for-loop displays 8 numbers, which are:

0 1 2 3 4 5 6 7 

Though the statement, "printf("%i ", i);" takes slightly longer to execute than a previous statement, "int N = 8;" or the last statement, "printf("\n");" , it is the statement of interest, and it is executed (N = 8) times. The statement of interest, "printf("%i ", i);" is the main operation, in this function.

Time complexity is the number of main operations in some piece of code. It is actually the maximum possible number of main operations in the code. In this situation, the first and last statements, "int N = 8;" and "printf("\n");" respectively, are ignored, when quoting the time complexity. They are also ignored, because they do not repeat. The repeating main operation, is called the dominant operation. Using the Big-O notation, the time complexity for this function is given as,

O(n)

where n in this case is 8. This is linear time, which can be appreciated as one complete scan of a list (consecutive counting).

Logarithmic Time – O(log n)

The mathematical symbol, =>, means “this implies that”.

Now,
8 = 2 x 2 x 2
=> 8 = 2³

In this second math statement, 2 is called the base, 3 is called the index and 8 is just called the number (number of interest). So 8 equals 2 raised to the power (index) 3, because 2 is multiplied by itself 3 times to give 8.

The second mathematical statement above, can be rewritten as:

        log₂ 8 = 3

read as, log to the base 2 of 8 equals 3. The word, log, is of the math topic, logarithm. There are three mathematical statements above (in this section). The second and third are two different ways of writing the same thing. The two different ways, each has its pros and cons.

From out of 8 possible repetitions of the main operation in a function, if the main operation repeats 3 times, then the time complexity is written as:

O(log₂ n)

using the Big-O notation, where n in this case is 8. The subscript 2 is optional to write. The logarithmic time, O(log n) is usually less than half the linear time, O(n), e.g 3 is less than half of 8, which is 4.

For code example of logarithmic time, with the number 8, consider the following function:

    void solution() {
        int N = 8;
        while (N > 1) {
            N = N / 2;  //integer division
            printf("%i, ", N);
        }
        printf("\n");
    }

The main operation consists of the two statements:

            N = N / 2;  //integer division
            printf("%i, ", N);

With integer division (N / 2), the remainder is abandon after each division. The output is:

4, 2, 1,

That is, out of 8 possible operations, there are 3 operations, corresponding to the 3 numbers at the output. With time complexity, what matters is the number of main operations, and not necessarily, the number of numbers at the output. In this situation, the number of numbers at the output happens to be the same as the number of main operations (number of round loopings (iterations)). For each loop repeat, the main operation executes in constant time, O(1). For the 3 repeats, the function takes logarithmic time, O(3) as opposed to linear time O(8), out of 8 operations.

Quadratic Time - O(n²)

In the alphabet, A, B, C, D, E, F, G, H are characters, and each is less than (comes before) 'I'. Consider the following function:

    void solution() {
        for (char i='A'; i<'I'; i++) {
            for (char j='A'; j<'I'; j++) {
                printf("%c ", j);
            }
            printf("\n");
        }
    }

There are two for-loops, with one nested in the other. The inner-loop prints a row of 8 characters. The outer-loop enables the printing of 8 of these rows. The output is:

    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 

This is an 8-by-8 table. The number of characters are 64 = 8 x 8. The main operation is 'printf("%c ", j);', which executes 8 x 8 times = 64 = 8²; that is 8 square. Squaring means quadratic. So the time complexity for this function is written as:

O(n²)

where n is 8 in this case. 8² = 8 x 8. This is quadratic time complexity.

n.log₂n Time

n.log₂n means, n x log₂n . The mathematical symbol, ∴ means, therefore.

From above,

      8 = 2 x 2 x 2
=>    8 = 2³
=>   log₂ 8 = 3

Now,

    if n = 8, then O(n²) = 64 operations = O(8²).

    if n = 8, it means log2 8 = 3;
    ∴ n x log2n = 8 x 3 = 24

64 = 8²

There are 24 main operations for (8xlog₂ 8) time. 24 is less than half of 64, which is 32. 24 is greater than 3, which equals log₂8

So, O(n.log₂n) time complexity lies between O(log₂n) and half of O(n²) , generally.

For code example of O(n.log₂n) time, with the number 8, consider the following function:

    void solution() {
        int N = 8, Q = 8;
        for (int i=0; i<Q; i++) {
            while (N > 1) {
                N = N / 2;  //integer division
                printf("%i, ", N);
            }
            printf("\n");
            N = 8;
        }
    }

The main operation consists of the two statements:

                N = N / 2;  //integer division
                printf("%i, ", N);

With integer division, the remainder is abandon after each division. The while-loop does the main operation, 3 times. The for-loop does what is in the while-loop 8 times. This makes 8 x 3 = 24. The exact time complexity from O(n.log₂n) here, is O(8.log₂ 3) . The output is:

    4, 2, 1, 
    4, 2, 1, 
    4, 2, 1, 
    4, 2, 1, 
    4, 2, 1, 
    4, 2, 1, 
    4, 2, 1, 
    4, 2, 1,

There are 8 rows and 3 columns, giving 24 output entries; in this case, corresponding to 24 main operations.

n + m Linear Time : O(n + m)

For code example of n + m linear time, with the number n = 8, consider the following function:

    void solution() {
        int start = 1;
        for (int i=start; i<8; i++) { 
            printf("%i ", i);
        }

        printf("\n");

        for (char i='A'; i<'J'; i++) {  //'I' is 9th letter in alphabet
            printf("%c ", i);
        }
        printf("\n");
    }

The main operation is "printf("%i ", i);" or "printf("%c ", i);" for either non-nested for-loops. The output is:

    1 2 3 4 5 6 7
    A B C D E F G H I

The first for-loop in the code, produces 7 out of 8=n main operations. The second for-loop in the code, produces 9 out of 8=n main operations. The first set of main operations is referred to as, n operations; and the second set of main operations is referred to as, m operations. Here, n + m = 7 + 9 = 16 (or about 16).

Here, n + m = 16 operations lies between the particular time complexity O(log₂ 8) = 3 operations, and the particular time complexity O(8.log₂ 8) = 24 operations. n + m time generally lies between O(log₂ n) time and O(n.log₂ n) time.

Even if there were three non nested for-loops, as in the following code, the time complexity would still be given as O(n + m) :

    void solution() {
        int start = 1;
        for (int i=start; i<8; i++) { 
            printf("%i ", i);
        }
        printf("\n");
        char ch = 'A';
        for (char i='A'; i<'I'; i++) {  //'I' is 9th capital letter in alphabet
            printf("%c ", i);
        }
        printf("\n");
        char c = 'a';
        for (char i='a'; i<'j'; i++) {  //'j' is 10th small letter in alphabet
            printf("%c ", i);
        }
        printf("\n");
    }

The output is:

    1 2 3 4 5 6 7
    A B C D E F G H 
    a b c d e f g h i

Nuance to do with ½n, 2n, etc.

In an algorithm where the upper limit is 8 = n (linear time), 4 main operations = ½n or 16 main operations = 2n, is given simply as O(n). In other-words, fractions and multiples (coefficients) in front of time complexity expressions are avoided.

Exponential Time Complexity : O(2ⁿ)

21 = 2
22 = 2 x 2
23 = 2 x 2 x 2
24 = 2 x 2 x 2 x 2
25 = 2 x 2 x 2 x 2 x 2

This is generally written as:

2ⁿ = 2 x 2 x 2 - - - x nᵗʰ2

2ⁿ is called the nᵗʰ power of 2. Time complexity of O(2⁵) means, there are 2⁵ = 2 x 2 x 2 x 2 x 2 = 32 main operations. In general, O(2ⁿ) means, there are 2ⁿ operations (maximum).

Multiplication is continuous addition; so 2⁵ = 2 x 2 x 2 x 2 x 2 = 32, is the same as:

    1 + 1 +
    1 + 1 + 
    1 + 1 + 1 + 1 + 
    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 
    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 

The main operation is just addition. There are 31 addition operations here. However, as concerns time complexity, the number of additions are assumed to be 32 (upper limit).

The following function is supposed to be for 2⁵ main operations, of time complexity, O(2⁵), and generalized as O(2ⁿ) . The first two main operations are outside the nesting loop.

    void solution() {
        int n = 5;

        int number = 1 + 1;
        int sum = 1 + 1;
        for (int i=2; i <= n; i++) {
            for (int j=1; j <= sum; j++) {    //last 3 rows above, approached in halves
                number = number + 1;
            }
            sum = number;
        }
        printf("%i\n", number);
    }

The output is 32. The statements, "int number = 1 + 1;" and "int sum = 1 + 1;" form the first two main operations in the code of interest. There are twenty eight more coded additions, each of which is just the addition of 1. The statements in the parentheses of the nesting for-loops are ignored, in determining the time complexity. The statements, "sum = number;" and 'printf("%i\n", number);' are also ignored. The reader should read through the function again, to really understand what is going on.

The code does 30 coded additions in the nested for-loop, and two additions outside the nesting for-loop; but the 5 rows of manual additions of 1’s, has 31 addition operations. That is how time complexity is, sometimes. The time complexity for this situation, is given as O(2⁵), and generalized as O(2ⁿ).

Factorial Time Complexity : O(n!)

Now,

      5! = 5 x 4 x 3 x 2 x 1 = 120
=>    5! = 120

Notice that x1 (times 1) does not change the previous product of x2.

Multiplication is continuous addition; so the above is the same as:

    (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) = 20 +

    (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) = 40 +

    (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) = 60 +

    (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) = 80 +
    (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) = 100 +
    (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) = 120

All the 1’s counted in this series gives 120. However, there are 119 addition operations in the series. Accept that.

The 1’s are in two groups for x2 (times 2). The first group has 1’s in three rows for x3. Each row is five 1’s times four. The second group also has 1’s in three rows . Each row is five 1’s times four.

The following function is for 5! = 120 main operations, of time complexity, O(5!), and generalized as O(n!) . The first main operation is outside the nesting for-loop.

    void solution() {
        int n = 5;
        int newAddition = 5;
        int oldAddition = 5;

        int factorial = 0;
        for (int i = n; i>1; i--) {
            for (int j=1; j <= newAddition; j++) {
                factorial = factorial + 1;
            }
            newAddition = factorial * (i - 1) - oldAddition;
            oldAddition = factorial * (i - 1);  //5 x 4 = 20, then 20 x 3 = 60. then 20 x 2 = 120. x1 (times 1) does not change the previous product of x2
        }
        printf("%i\n", factorial);
    }

The output is 120. There are 119 addition operations in the code. The time complexity is given as O(120), and not O(119), and generalized as O(n!). Accept that. The main operation is "factorial = factorial + 1;", where factorial is just a variable; and the rest of the operation statements in the code, are ignored, in the quotation of time complexity – accept that. If n = 4, then all the values of 5 in the code, have to be changed to 4. The reader should read through the function to really understand what is going on.

Time limit

Nowadays, an average computer can perform 10⁸ operations in less than a second. Sometimes the programmer has the information he needs about the expected time complexity, but at other times the programmer does not.

During contests, the candidate is often given a limit on the size of data; and therefore he can estimate the time complexity within which the task should be solved. This is usually a great convenience because he can look for a solution that works in a specific time complexity, instead of worrying about a faster solution. For example, at codility.com, if the size of the data:

    -  n <= 1 000 000, the expected time complexity is O(n) or O(n log n),
    -  n <= 10 000, the expected time complexity is O(n² ),
    -  n <= 500, the expected time complexity is O(n³ ).

Of course, these limits are not precise. They are just approximations, and will vary depending on the specific task.

Approximation of Time Complexity

Time complexity, of O(10) may actually have 8 or 9 operations, or even 11 or 12 operations, or the 10 itself, though the maximum limit of 8 is aimed at. In many cases it would have 8 operations or less.

Exercise

Problem 1: You are given an integer n. Count the total of 1 + 2 + . . . + n, in O(n²) time.
Solution
The following program has one test case in the main() function (read the code and comments in the whole program). In the function, 1 is 1; 2 is 1 + 1; 3 is 1 + 1 + 1; 4 is 1+1+1+1; etc.

    #include <stdio.h>

    int slow_solution (int N) {  //using zero based indexing 
        int result = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j < i+1; j++) {  //i=0 or j=0 refers to the first element, 1
                result += 1;               //i=1 or j=1 refers to the second element, 2, etc.
            }
        }

        return result;
    }

    int main(int argc, char **argv)
    {
        int n = 4;
        int res = slow_solution(n);
        printf("%i\n",res);

        return 0;
    }

The output is 10, for input of N = 4.

Problem 2: Repeat the above problem for the time complexity of O(n).
Solution
The following program has one test case in the main() function (read the comments in the whole program). The function does 1 + 2 + 3 + 4 = 10.

    #include <stdio.h>

    int fast_solution (int N) {  //using zero based indexing 
        int result = 0;
        for (int i=0; i<N; i++) {
            result = result + (i + 1);  //1=0+1; 2=1+1; 3=2+1; etc.
        }

        return result;
    }

    int main(int argc, char **argv)
    {
        int n = 4;    //1 + 2 + 3 + 4 = 10
        int res = fast_solution(n);
        printf("%i\n",res);

        return 0;
    }

The output is 10; same as above, for input of N = 4.

Problem 3: Repeat the above problem for the constant time complexity, O(1).
Solution
This is a mathematical Arithmetic Progression, with the first term, a = 1, and common difference, d = 1. The sum, Sₙ of the first n terms, of an arithmetic progression, is given by,

    Sₙ = n/2[2a + (n-1)d]

This formula is one main operation and should be coded as such. The following program has one test case in the main() function (read the comments for the whole program):

    #include <stdio.h>

    int model_solution (int n) {  //formula: sum of arithmetic progression, with first element, 1 and difference, 1

        int result = n/2*(2*1 + (n-1)*1);  //one operation, without repetition in any loop

        return result;
    }

    int main(int argc, char **argv)
    {
        int n = 4;  //sum = n/2*(2*1 + (n-1)*1)
        int res = model_solution(n);
        printf("%i\n",res);

        return 0;
    }

The output is 10; same as above, for input of N = 4. There is only one main operation here.

Space Complexity

Memory limits provide information about the expected space complexity. The programmer can estimate the number of variables that he can declare in his programs. In short, if he has constant numbers of variables, he also has constant space complexity: in Big-O notation this is O(1). If he needs to declare an array with n elements, he has linear space complexity - O(n).

More specifically, space complexity is the amount of memory needed to perform the computation. It includes all the variables, both global and local, dynamic pointer data-structures, and in the case of recursion, the contents (space) of the stack. Depending on the convention, input data may also be included. Space complexity is more tricky to calculate than time complexity, because not all of these variables and data-structures may be needed at the same time. Global variables exist and occupy memory all the time; local variables (and additional information kept on the stack) will exist only during invocation of the function. There are also temporary variables needed by the algorithm.

In many problems, it is the time complexity that is expected to be met, and the space complexity limit is not indicated.

Whatever is the case, space complexity is explained in the next part of the series.

Conclusion

The time complexity of a piece of code, is the number of main operations in the code. This is a good indication of how fast the code will run on a particular system (computer). The main operation may consist of one, or two or three simple statements.

If the main operation consists of many statements, then single statements sprinkled here and there in the code, will be ignored in the quotation of the time complexity.