Time Complexity in Data Structure

Time Complexity

In simple term time complexity is the notation which is used to represent the time which is taken by any algorithm to procedure it's task based on given input

Larger input -> Longer time

Small input -> Short time

There are mainly two types of algorithms

• Runs on constant time O(1) (Big Oh of 1)
• Time depend on the number of input O(n) (Big Oh of n)

Below graph represents the slopes of different notations

Consider the example

Below noted table shows the time taken by two different algorithm for sorting an array

No. of elements	Algorithm 1	Algorithm 2
10	90ms	122ms
80	110ms	124ms
150	180ms	131ms
1400	2s	800ms

What do you think which algorithm is better ?

Well it totally depends on the useCase

for longer list Algorithm 2 is better as it runs on constant time and for shorter list Algorithm 1 is better which runs on linear time

Notations ranks based on time which they consumes

• O(1) Constant time <------------------Best
• O(log ₙ) Log base n time input
• O(n) Linear time
• O(n²) Double the linear time <----------------Worse

There are many more notations but these are common notations which are used widely

Note

In time complexity we ignore the non dominant term which doe'nt affect on overall calculation e.g. Declaration of variables

Calculating time complexity

consider the example which adds element in array in c language.

// constant time k
int a = 0;
int arr[10];
// calculation time f(n)
for (int i = 0; i < 10; i++)
{
    arr[i] = i + 1;
    printf("Element %d\n", arr[i]);
}

The time complexity of above code is O(n) as the time taken to add element in array depends on variable b

Output of above snippet

Element 1
Element 2
Element 3
Element 4
Element 5
Element 6
Element 7
Element 8
Element 9
Element 10

Quick quiz

What is the time complexity of given code

int a = 0;
int b = 10,c = 20;
int arr[b],arr1[c];


for(int i = 0; i < b; i++)
{ 
    arr[i] = i+1;
    printf("Element in arr 1: %d\n",arr[i]);
}

for(int j = 0; j < c; j++)
{ 
    arr1[j] = j+1;
    printf("Element in arr 2: %d\n",arr1[j]);
}

and of this one

int k = 10;

for(int i = 0; i < k; i++)
{
    printf("\nValue of i = %d\n",i);
    // Performs some complex tasks apart printing
    for(int j = 0; j < k; j ++)
    {
        // Performs some complex tasks apart printing
        printf("Value of j = %d",j);
    }
}

Answers

---

First one: O(n)

Explanation: The both loops are independent and they both takes same amount of time O(n) but we can't represent time in 2*O(n)

---

Second one: O(n²)

Explanation: The first loop takes time O(n) while the loop inside the first loop also takes time of O(n), therefore O(n) + O(n) * n = O(n²)