Time Complexity Of Algorithms

The time complexity of an algorithm is the time required for an algorithm for its complete execution.The time complexity of an algorithm usually depends on the size of the input.

Some common time complexities

The time complexity of various algorithms would be constant O(1),Linear O(n),quadratic O(n2),Exponential O(2n),factorial O(n!) etc

Now let us see some of the time complexities.

O(1)

The time complexity of an algorithm is said to be O(1),If it requires same amount of time for execution regardless of the size of the input.

Example:

It takes constant time to access an element in an array of any size.

O(n)

The time complexity of an algorithm is said to be O(n),If the time of execution of the algorithm increases linearly with increase in size of the input.

Example

int main(void) {
int arr[5],i;
printf("enter 5 integers\n");
for(i=0;i<5;i++)
scanf("%d",&arr[i]);
printf("It takes linear time access the elements of an array\n");
for(i=0;i<5;i++)
printf("%d",arr[i]);
 return 0;
}

Output

enter 5 integers
1
2
3
4
5
It takes linear time access the elements 
of array
12345

O(logn)

The time complexity of an algorithm is said to be O(logn),If the time of execution of the algorithm increases logarithmically with increase in size of the input.

O(loglogn)

The time complexity of an algorithm is said to be O(loglogn),If the loop variables are increased or decreased by a constant amount.

int main() 
{
 
int i,n=2,c=3;
for(i=2;i<=n;i=pow(i,c))
printf("Code Titans\n");
return 0;
}

Output

Code Titans

O(n^c)

The time complexity of an algorithm is said to be O(nc) which is nothing but the time required to execute the innermost loop.

Example for n²

int main() {
int i,j;
for( i=0;i<3;i++)
{
    for(j=0;j<2;j++)
    {
        printf("Code Titans\n");
    }
}
 return 0;
}

Output

Code Titans
Code Titans
Code Titans
Code Titans
Code Titans
Code Titans

O(cⁿ)

The time complexity of an algorithm is said to be O(cⁿ),If the time of execution of the algorithm increases exponentially with increase in size of the input.

Example

Brute force method of n-queen problem take O(nⁿ)

O(n!)

Some algorithms take factorial time for their execution which are considered as the slowest algorithms.

Example

Travel Sales person