Analysis of Loops – Asymptotic Notation

Here, We learn about the analysis of loops like O(1), O(n), O(n^c), 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(n^c)

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

Selection Sort and Insertion Sort have O(n²) time complexity.

For example, the following sample loops have O(n²) 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! > 4ⁿ > 2ⁿ > n² > n(logn) > log(n!) > n > 2^logn > log²n > √(logn) > log(logn) >1

---

Related:

---

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 contribute@totheinnovation.com. See your articles on the main page and help other coders.😎