Analysis of Loops – Asymptotic Notation

Here, We learn about the analysis of loops like O(1), O(n), O(nc), O(log n), O(log log n) and O(m+n) in terms of time complexity and order of growth of functions in the algorithm.

Analysis of Loops

1. O(1)

Time complexity of a function (or set of statements) is O(1). It doesn’t contain loop, recursion and call to any other non-constant time function.

For example, the following loop have O(1) time complexity.

// Here c is a constant for (int i=1; i<=c; i++) { //some O(1) expressions }
Code language: C++ (cpp)

2. O(n)

Time Complexity of a loop is O(n) if the loop variables are incremented/decremented by a constant value.

For example, the following sample function have O(n) time complexity.

// Here c is a positive integer constant for (int i=1; i<=n; i+=c) { //some O(1) expressions } for (int i=n; i>0; i-=c) { //some O(1) expressions }
Code language: C++ (cpp)

3. O(nc)

Time Complexity of nested loops is O(nc) if the number of times the innermost statement is executed.

Selection Sort and Insertion Sort have O(n2) time complexity.

For example, the following sample loops have O(n2) time complexity.

for (int i=1; i<=n; i+=c) { for (int j=1; j<=n; j+=c) { //some O(1) expressions } } for (int i=n; i>0; i+=c) { for (int j=i+1; j<=n; j+=c) { //some O(1) expressions } }
Code language: C++ (cpp)

4. O(log n)

Time Complexity of a loop is O(log n) if loop variables is divided/multiplied by a constant value.

main() { i=1; while (i<n) { i=2*i; } }
Code language: C++ (cpp)

In above code, statement inside the code runs (log n) times.

5. O(log log n)

Time Complexity of a loop is O(log log n) if loop variables is reduced/increased exponentially by a constant value.

// Here c is a constant greater than 1 for (int i=2; i<=n; i=pow(i,c)) { //some O(1) expressions } // Here fun is sqt or cuberoot or any other constant root for (int i=n; i>0; i=fun(i)) { //some O(1) expressions }
Code language: C++ (cpp)

6. O(m+n)

Time Complexity of consecutive loop is O(m+n) mean sum of time complexities of individual loops.

for (int i=1; i<=m; i+=c) { //some O(1) expressions } for (int i=1; i<=n; i+=c) { //some O(1) expressions }
Code language: C++ (cpp)

Time complexity of above code is O(m)+O(n) which is O(m+n).

Growth of Functions

The order of growth of the running time of an algorithm gives a simple characterization of the algorithm’s efficiency.

The decreasing order of growth of time complexity is

n! > 4n > 2n > n2 > n(logn) > log(n!) > n > 2logn > log2n > √(logn) > log(logn) >1


Analysis of Algorithms

Algorithms Analysis help us to determine which algorithms are more efficient. Types of analysis:-Worst, Best, Average. How to Compare two Algorithms? Algorithm Complexity – Space Complexity, …
Read More

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to [email protected]. See your articles on the main page and help other coders.

Leave a Comment

Your email address will not be published. Required fields are marked *