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}**)**

^{c}

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

Selection SortandInsertion Sorthave O(n^{2}) time complexity.

For example, the following sample loops have O(n^{2}) 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 ^{n} > 2^{n} > n^{2 }> n(logn) > log(n!) > n > 2^{logn} > log^{2}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 **[email protected]**. See your articles on the main page and help other coders.