Do you Know? In how many ways, you can express your algorithm?

There are two ways to express your algorithms-

1. Iterative Algorithms

2. Recursive Algorithms

Recursive algorithms can be converted into iterative algorithms and iterative algorithms can be converted into recursive algorithms, both have same in power.

We will see the examples of both types of algorithm in further post.

Guidelines for Asymptotic Notations:

So, there are some rules that you have to follow. These rules help us to determine the time complexity (running time) of the algorithm.

1. Non-Recursive and Non-Loop Statements:

If any algorithm doesn’t contain loop, recursion and call to any other non-constant time algorithm, then the time complexity of this type of algorithm is considered as O(1) or linear time complexity.

Example 1- swap() algorithm has O(1) time complexity.

Example 2- If a loop or recursion that runs a constant number of times. Then, this loop or recursion is also considered as O(1) time complexity. Here is the example- (c-constant) 

Hence, Time Complexity = O(1)

2. Loop Statements:

The running time of a loop, can be expressed as the running time of the statements inside the loop (including tests) multiplies by the number of iterations.

Example 1-

Hence, Time Complexity = c*n = O(n) 

or

There is one more definition for this section, i.e., Time complexity of a loop can be considered as O(n), if the variable used in loop is incremented/decremented by a constant value.

Example 2-

Here, c – positive integer constant

Hence, Time Complexity = O(n)

3. Nested Loop Statements:

If we have to analyze the time complexity of the nested loop statements, then always analyze from the inside out. Total time complexity is the product of the sizes of all the loops.

Example-

Hence, Time Complexity = c*n*n = c*n2 = O(n2)

4. Consecutive Loop Statements:

In the case of consecutive loop statements, add the time complexities of individual loops.

Example-

Hence, Time Complexity = O(m) + O(n) = O(m+n) 

5. Logarithmic Complexity:

Time complexity of a loop is considered as O(logn), if the loop variable is multiplied/divided by a constant value.

Example 1-

Hence, Time Complexity = O(logcn) 

or we can say that, in the above example, the loop runs (logcn) times.

Why here is ‘c’ in the log base? 

Let c=2 in the above example,

i : 1, 2, 4, 8,……, n

i : 20, 21, 22, 23,…., 2k   

Hence, n = 2k 

Taking logarithm in both sides,

log2n = k*log22

k = log2n 

Hence, T(n) = O(log2n)

and

Time complexity of a loop is considered as O(loglogn), if the loop variable is reduced/increased exponentially by a constant value.

Example 2-

Hence, Time Complexity = O(logclogn)

Why here is ‘c’ in the log base? Try to prove it. Take c=3,4….or some other constant value.