How To Calculate Time Complexity And Space Complexity Of An Algorithm – Big O Notation Examples

How to calculate time complexity and space complexity of an algorithm show developers who are new to the subject what Big O Notation is about using examples.

Let’s look at this C function to Remove Duplicates From Sorted Array In C – Using Two Pointers for example

int removeDuplicates(int* nums, int numsSize){        
    int i=0;
    int len = 0;
    
    for(i=0; i<numsSize-1; i++)
        if(nums[i] != nums[i+1])
            nums[len++] = nums[i];
            
    nums[len++] = nums[numsSize - 1];
    
    return len;
}

which is called in the main function below

int main()
{
    int ary[8] = {0,0,0,0,1,1,12,400};
    int i;
    int sz = sizeof(ary)/sizeof(ary[0]);

    int new_arry_length = removeDuplicates(ary, sz);     
    printf("New lenght is: %d", new_arry_length);
    
    return 0;
}

Time Complexity Calculation

All algorithms that solve a given problem are analyzed in terms of the input size

So the main thing about time complexity is to find out how much time a program takes to execute as the input size increases.

So to calculate the time complexity for our function removeDuplicates which takes an array of size sz == 8, you should take this 2 steps:

1. Find the count of time each line of code gets executed
2. Sum all the counts to get the equation or the Big O

Lets’ use the below table to summarize the number of times each line of code gets executed:

Each line of code	No. of executions
int i=0;	1
int len = 0;	1
for(i=0; i<numsSize-1; i++)	8
if(nums[i] != nums[i+1])	7
nums[len++] = nums[i];	2 worst case 7 (no repeated array element)
nums[len++] = nums[numsSize - 1];	1
return len;	1

Now to sum up all counts together, we have:

1 + 1 + 8 + 7 + 7 + 1 + 1 (note we are using worst case count for this line: nums[len++] = nums[i];)

The lines of code with count 8 and 7 and 2 (or worst case 7) all depends on the input size; the for loop terminated when the variable i became 7 (which equals 8 count for a zero based array) and the if statement inside the for loop executed 7 times out of n times where n is the size of the input array and the size is equal to 8 elements.

So putting the equation in perspective in terms of input size, we have:

1 + 1 + n + (n – 1) + (n – 1) + 1 + 1 Where n is the input size and n == 8,

Therefore simplifying the mathematical expression, the complexity becomes:

3n + 2

Also notice that every other line of code does not depend on the given array at all and thus executes only once or at a constant time every time.

Deriving The Big O Notation Of Our Algorithm

So we can then use our derived complexity to calculate our Big O Notation.

Three things are necessary to do to get the Big O out of the time complexity:

1. Identify the fastest growing term in the equation derived
2. Remove constant from the derived equation
3. Remove co-efficient from the fastest growing term if any
4. What is left is the Big O

So for our derived time complexity 3n + 2, the fastest growing term is 3n and the constant in the equation is 2. So we remove 2 from the equation, we are left with 3n; and then we remove the coefficient from the fastest growing term which is 3 and we are left with n. The Big O Notation of our algorithm is therefore O(n) and the algorithm runs at linear time.

But O(n) is not the only runtime complexity of algorithms there is. See table of different types of time complexity below:

Type of Time Complexity	Name	Explanation
O(1)	Constant	f(n) = 1 —–> Constant time f(n) = 2 —–> still Constant time f(n) = 5 —–> still Constant time f(n) = 2000 —–> still Constant time
O(logn)	Logarithmic
O(n)	Linear	f(n) = 3n + 2 —–> O(n) f(n) = 500n + 200 —–> still O(n) f(n) = n/500 + 2 —–> still O(n)
O(n2)	Quadratic
O(n3)	Cubic
O(2n)	Exponential	Could be O(3n) up to O(nn)

Look here https://www.bigocheatsheet.com/ to have a broad list of other types of time complexities.

Okay, lets look at another example with a two-dimensional array with n number of rows and n number of columns (i.e n² elements) as input:

#include <stdio.h>

int Sum_Of_Array_Elements(int arr_2d[3][3], int rSize, int cSize){
    int i;
    int y;
    int Total = 0;
    for(i=0; i<rSize; i++)
        for(y=0; y<cSize; y++)
            Total += arr_2d[i][y];
            
    return Total;
}

int main()
{ 
    int Array_2d[3][3] = {{1, 4, 3},
                          {3, 1, 9},
                          {0, 5, 2}};
    
    int Arry_Sum = Sum_Of_Array_Elements(Array_2d, 3, 3);     
    printf("Array size is: %d\n", Arry_Sum);
    
    return 0;
}

Deriving The Time Complexity And Big O Notation Of The Function Sum_Of_Array_Elements

To determine the time complexity and the Big O Notation of our function Sum_Of_Array_Elements above, we have to go through the same process as before.

Again, lets’ use the below table to summarize the number of times each line of code gets executed:

Each line of code	No. of executions
int i;	1
int y;	1
int Total = 0;	1
for(i=0; i<rSize; i++)	4
for(y=0; y<cSize; y++)	3 * 4
Total += arr_2d[i][y];	3 * 3
return Total;	1

Sum Up No. of executions

1 + 1 + 1 + 4 + (3 * 4) + (3 * 3) + 1

Our input is a 3 by 3 2d array. The outer for statement terminates when i becomes 3 (i.e 0, 1, 2, 3); meaning it gets executed 4 times, and the inner for statement also executed 4 times. But all statements inside the outer for loop gets executed only 3 times; hence the inner for statement gets executed 3 * 4 times while the statement Total += arr_2d[i][y]; gets executed only 3 * 3 times. Every other statement in the code happens only 1 time every time this code is executed.

The input size in terms of rows and columns in our given array is:

• rows == 3
• columns = 3

1 + 1 + 1 + 4 + (3 * 4) + (3 * 3) + 1 becomes 1 + 1 + 1 + (3 + 1) + (3 * (3 + 1)) + (3 * 3) + 1

1 + 1 + 1 + (3 outer loops 1 per row + 1 extra outer loop which causes condition to become false) + (3 outer loops 1 per row * (3 inner loops 1 per column + 1 extra inner loop which causes condition to become false)) + (3 outer loops 1 per row * 3 inner loops 1 per column) + 1

So putting the equation in perspective in terms of input size n:

1 + 1 + 1 + (3 + 1) + (3 * (3 + 1)) + (3 * 3) + 1 becomes 1 + 1 + 1 + (n + 1) + (n * (n + 1)) + (n * n) + 1

which becomes 1 + 1 + 1 + n + 1 + n² + n + n² + 1,

which becomes 2n² + 2n + 5

So we arrive at the equation 2n² + 2n + 5 as the time complexity for our function.

The Big O Notation For Our Function Sum_Of_Array_Elements

1. Identify the fastest growing term in the equation derived
2. Remove constant from the derived equation
3. Remove co-efficient from the fastest growing term if any
4. What is left is the Big O

• So the fastest growing term of the equation 2n² + 2n + 5 is 2n²
• As we remove constant 5 and the slower growing term 2n from the equation, we are left with just the fastest growing term 2n²
• We then remove the coefficient from the fastest growing term and we are left with n²
• n² is what goes into our big O Notation, so the big O Notation for our function is O(n²)

Lets see an example with a triple for loop this time

int Sum(int arr[][n], n){
    int i, j, k, sum = 0;
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            for(k=0; k<n; k++){
                sum = sum + arr[i][j];
            }
        }
    }
    return total;
}

Deriving The Time Complexity And Big O Notation Of The Function Sum

See attached image below for a summary of the number of times each line of code gets executed:

To sum up the Time Complexity in terms of n where n is the input size, we have:

1 + (n + 1) + (n * (n + 1)) + (n * n * (n + 1)) + (n * n * n) + 1 which becomes:

1 + n + 1 + n² + n + n³ + n² + n³ + 1 which becomes:

2n³ + 2n² + 2n + 3

Okay so as before,

• Identify the fastest growing term in the equation derived

The fastest growing term is obviously 2n³

• Remove coefficient from the fastest growing term

The coefficient in the fastest growing term is 2; once removed we are left with n³ and this is what goes into the big O, hence the big O of our function Sum is O(n³).

What if our code rather looks like this:

int Sum(int arr[], n){
    int i, sum = 0;

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

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

    return sum;
}

Time Complexity Of Two for loops Not Nested

See attached image below for a summary of the number of times each line of code gets executed:

To sum up the Time Complexity in terms of n where n is the input size, we have:

1 + (n + 1) + n + (n + 1) + n + 1 which becomes:

4n + 4

Now to calculate the big O Notation from the derived time complexity 4n + 4,

• Identify the fastest growing term in the equation derived

The fastest growing term of the equation is 4n

• Remove coefficient from the fastest growing term

The coefficient in the fastest growing term is 4; once removed we are left with n and this is what goes into the big O, hence the big O of our function Sum with two loops is O(n).

So what we observe here is that having a separate loop does not have any major effect in the time complexity. So here we can conclude that if an algorithm has n separate loops (where n is the no. of separate loops in the entire algorithm), then the Time complexity of the entire algorithm will be the Time Complexity of the loop with the highest Time Complexity. In this instance each of the for loop has time complexity of O(n), it doesn’t matter how many separate for loops were in that code as far as each of them had time complexity of O(n) then the overall time complexity of the entire algorithm is always going to be O(n); but if one of the separate for loop has time complexity of O(n²), then the overall time complexity of the entire algorithm is going to be O(n²).

What if our code example for Time Complexity Of Two for loops Not Nested was rather like this:

int p=0;
for(i=1; i<n; i=i*2){
    p++;
}
for(i=1;j<p;j=j*2){
    //some stmt here
}

See table below for time complexity of each statement

Statement	Time Complexity
p++	logn
//some stmt here	logp

For simplicity i have omitted the for statements (the result will be same even if we added them).

Okay so the statement p++ has time complexity of logn based on the conditions of the for loop in which it is contained in. So we can say that p = logn

If you substitute p in logp (which comes from //some stmt here), we get

logp = log(logn) = log logn; hence the time complexity of this particular non nested for loop is loglogn.

Lets see an example that arrives at O(1) i.e such a function runs at constant time – meaning that no matter how an input size grows the time it takes for the function to complete it task remains constant.

#include <stdio.h>

int Silly_Function(int* given_array){
    int total;
    total = 0;

    return total;
}

int main()
{ 
    int given_array[] = {0,1,1,0,0};
    
    int Total = Silly_Function(given_array);     
    printf("Total is: %d\n", Total);
    
    return 0;
}

Okay so take a look at our function Silly_Function, it does nothing with the given input; all it does is assign the value 0 to the variable total and then return total each time.

Each line of code	No. of executions
int total;	1
total = 0;	1
return total;	1

Summing up all count of execution we have: 1 + 1 + 1 which is equal to 3 and can be re-written as:

3 * 1 where 3 is the coefficient and as such what goes into the Big O Notation is 1,

Therefore the Big O Notation of our Silly_Function is O(1) and the function will run at constant time each time.

Time Complexity And Big O Notation For Different For Loops

Time Complexity Of For Loop With i=i*2

for(i=1; i<n; i=i*2){
    //some stmt here
}

Let us consider the variable i using the table below

No. of Passes for For Loop	Value of i for Each Pass
1st Pass	i = 1 (i.e initialization)
2nd Pass	i = 1 * 2 = 2
3rd Pass	i = 2 * 2 = 22
4th Pass	i = 22 * 2 = 23
……	……
……	……
……	……
Kth Pass	i = 2k

From the table we can see that at the Kth Pass (and we don’t know what that K value might be), i = 2^k

Using the assumption that the For Loop terminates when

i >= n

which we can re-write as

i = n (still holds true)

now we from our table above that i = 2^k and so substituting i in

i = n

we have

2^k = n

k = log₂n

Therefor the For Loop will execute for O(logn) runtime.

Note that in our For Loop statement if i = i * 3 instead of i = i * 2, then k would have been k = log₃n. Of course this will still amount to O(logn).

Time Complexity Of For Loop With i=i/2

for(i=n; i>=1; i=i/2){
    //some stmt here
}

For i 1st pass, 2nd pass, 3rd pass, 4th pass, …, …, …, up to kth pass, we have:

i = n (initialization), n/2, n/2², n/2³, n/2⁴, …, …, …, up to n/2^k

Using the assumption that the For Loop terminates when

i < 1

which we can re-write as

i = 1

and substitute i in

i = 1

we have

n/2^k = 1 which becomes,

2^k = n,

k = log₂n

Therefor the For Loop will execute for O(logn) runtime.

Note that in our For Loop statement if i = i/3 instead of i = i/2, then k would have been k = log₃n. Of course this will still amount to O(logn).

Time Complexity Of Nested for loop Where j=j*2

for(i=0; i<n; i++){
    for(j=1; j<n; j=j*2){
        //some stmt here
    }
}

See table below for time complexity of each statement

Statement	Time Complexity
for(i=0; i<n; i++){	n
for(j=1; j<n; j=j*2){	n (for outer for statement) * logn (this is the complexity for this particular for statement) = nlogn
//some stmt here	nlogn (same as inner for statement)

To sum it up, we have:

n + nlogn + nlogn = 2nlogn + n

Obviously the highest growing term in the equation is 2nlogn and if we remove the coefficient from the highest growing term, we are left with nlogn.

So our runtime for this for loop is O(nlogn).

Lets look at another example of time complexity of 3 nested for loops where one of the inner loop is compared with a constant rather than with the input size n.

void tripleLoop(int n) {
   for (int j=0; j<n; j++) {
      for (int i=0; i<3; i++) {   
         for (int i=0; i<n; i++) {
             printf("The time complexity here is not O(n3)");
         }
      } 
   }
}

See table below for time complexity of each statement

Each line of code	Time Complexity
for (int j=0; j<n; j++) {	n + 1
for (int i=0; i<3; i++) {	n * (3 + 1)
for (int i=0; i<n; i++) {	n * (3 ) * (n + 1)
printf(“The time complexity here is not O(n3)”);	n

To sum things up, we have:

n + 1 + n * 3 + 1 + n * 3 * n + 1 + n which becomes n + 1 + 3n + 1 + 3n² + 1 + n,

which becomes: 5n + 3n² + 3

From the time complexity equation, you can see that the fastest growing term of the polynomial is 3n² and so if you remove the coefficient, what you have left is n²; hence, our time complexity for this 3 nested for loop is O(n²).

Summary Of Time Complexity For Different For Loops

For Loop	Time Complexity
for(i=0; i<n; i++)	O(n)
for(i=0; i<n; i=i+2)	O(n)
for(i=n; i>1; i–)	O(n)
for(i=1; i<n; i=i*2)	O(logn)
for(i=1; i<n; i=i/2)	O(logn)

So the thing we see about different big O Notations is that the different speed implication especially as input size increases. One of the concerns in this industry is the question: How does the runtime of your function grow as the input size increases? Now this is the real issue, this is why this is such a big interview point for interviewers. Employers want to know that you are writing codes with efficient time and space complexity.

Larger input sizes can be an issue to handle for inexperienced programmers. A program having quadratic runtime O(n²) which has to take array size of say 100,000 elements as input size can take forever to execute; so we must find better ways to write our algorithm such that it can run on a more efficient time complexity for such an amount of input – this is where learning of data structure and algorithm comes in.

Why Is Time Complexity Important

So you see everyone is diving into coding this days and majority of the people are self taught programmers. So self taught programmers who are probably still writing codes individual clients who themselves probably no nothing about scalability especially if their users are just a handful.

Time complexity begins to matter when you have to write codes that millions of users will use and you must know about what data structure and algorithm to use to achieve an acceptable execution time.

For instance lets look at an experiment; how much time it takes to sort a given array using two different algorithm (bubble sort and merge sort) as the array size increases.

Time Complexity Experiment

So we need to sort an array of integers of different size and we need to know which algorithm to use which will be more efficient considering time complexity i.e how long it will take the program to execute as the input size increases.

So for e.g if we have an input like this:

arr = {9, 6, 3, 9, 1}

our expected output should be:

arr = {1, 3, 6, 9, 9}

My interest here is not to show you how to write bubble sort or merge sort algorithm (you can google that if you don’t already know), but to show you how this two algorithm performed with different array sizes.

Bubble sort has a worst-case complexity of О(n²) while Merge sort has a worst-case complexity of O(nLogn).

So to see the implication of O(n²) against O(nLogn), i ran the experiment to see how long it takes the two algorithm (in seconds) to finish execution on my HP EliteBook Workstation icore 7 having 8G ram and the result is as tabulated below:

Input Size	Bubble Sort	Merge Sort
6000	0.09	0.009
12000	0.299	0.015
120000	24.719	0.026
1200000	2474.482	0.15

From the result, you can see that Merge sort is a far more efficient algorithm to use for this kind of sorting considering time complexity as the input size increase. Also look at the big O cheat sheet to see the difference between O(n²) and O(nLogn).

Space Complexity Of An Algorithm

For Space Complexity each Initialization of variable takes 1 unit of space

Now we look at space complexity of some of our algorithm above. Let’s start with this code:

int Sum(int arr[], n){
    int i, sum = 0;

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

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

    return sum;
}

See table below for variable initialization count:

Each line of code	Count of variable Initialization
int Sum(int arr[][n], n){	arr = n spaces, n = 1 space
int i, sum = 0;	i = 1 space, sum = 1 space
for(i=0; i<n; i++){	No new initialization of variable
sum = sum + arr[i];	No new initialization of variable
for(i=0; i<n; i++){	No new initialization of variable
sum = sum + arr[i];	No new initialization of variable
return sum;	No new initialization of variable

To sum up the Count of Variable Initialization we have:

n + 1 + 1 + 1 which becomes:

n + 3

• Identify the fastest growing term from the derived space complexity equation

The fastest growing term is n

• Remove constant form the derived equation and coefficient from the fastest growing term if any.

So we remove 3 from the equation and we are left with n; there is no coefficient attached to n so we return n as the term that should go into the big O Notation.

Our space complexity and big O Notation for our function Sum is O(n).

Another quick example, lets see this other code

int Sum(int arr[][n], n){
    int i, j, k, sum = 0;
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            for(k=0; k<n; k++){
                sum = sum + arr[i][j];
            }
        }
    }
    return total;
}

See table below for variable initialization count:

Each line of code	Count of variable Initialization
int Sum(int arr[][n], n){	arr = n rows * n cols = n2 units, n = 1 unit
int i, j, k, sum = 0;	i = 1 unit, j = 1 unit, k = 1 unit, sum = 1 unit
Statements after	No new initialization of variable

To sum up the Count of Variable Initialization we have:

n² + 1 + 1 + 1 + 1 + 1 which becomes:

n² + 5

• So we identify the highest growing term to be n²
• We remove the constant 5 from the equation and return n² as what should go into the big O Notation.

Therefore the space complexity for our function is O(n²)