Home Data Structures Understanding Time Complexity

Understanding Time Complexity

Time complexity is an approximation of how low it will take for an algorithm to execute. It is not an actual time(ex in sec/ns) but an approximate time. It is commonly estimated by counting the number of elementary operations performed by the algorithm.

Example: Suppose we have an array with n elements. Then if we traverse the entire array, then we have to visit each element exactly once and since there are n elements, we have to traverse all n elements. Hence here time complexity is n or O(n)

Various Notations to Represent Time Complexity:

Big O: It tells the upper bound on the time taken by an algorithm.
If f(x)<= c*g(n), then f(x) = O(g(x)). Here, c is constant and f(x) and g(x) are some function.

Big omega: It tells the lower bound on the time taken by an algorithm.
If c1*g(n) <= f(x), then f(x) = Ω(g(x)). Here, c is constant and f(x) and g(x) are some function.

Big Theta: It tells the tight bound on the time taken by an algorithm.
If c1*g(n) <= f(x)<= c2*g(n), then f(x) = Θ(g(x)). Here, c1,c2 are constants and f(x) and g(x) are some function.

for(i=0;i&lt;n;i++){
//do something
}

The complexity of the above code is O(n) since the loop is running n times.

for(i=0;i&lt;n;i++)
{
for(j=0;j<=n;j++)
//do something
}

The time complexity of the above code is O(n^2) as here are loops. First loop is running n times, and for every iteration of the first loop, the second loop is running n times.

 

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promise, we won't spam
Even we hate spam as much as you hate them

LEAVE A REPLY

Please enter your comment!
Please enter your name here