Complexity of Loops

The time complexity of a function is O(1) if does not contain a loop, recursive function, or any other non-constant time function. 

The time complexity of a loop is also O(1) if it has a constant no of iterations

Recursive function time complexity is also O(1) if it runs a constant no of times.

Linear Loops:

The time complexity of a loop is O(n) which is linear. If the loop variable is incremented or decremented by constant

Nested Loops: 

1. The time complexity of nested loops is equal to the number of times the innermost statement is executed. For example, the following sample loop has O(n2) time complexity:

   for (int i = 1; i <=n; i += c) {

       for (int j = 1; j <=n; j += c) {

          // some O(1) expressions

       }

   }

 

2. When one of the loops is divided and multiplied by constant and other loop is incrementing or decrementing by constant.

   for (int i = 1; i <=n; i += c) {

       for (int j = 1; j <=n; j /= c) {

          // some O(1) expressions

       }

   }

The time complexity of the above loop is The time complexity is O(nlogn).


Logarithmic Loops:

1. The Time Complexity of a loop is considered as O(log2n)  if the loop variable is divided/multiplied by a constant amount. Consider the following two for loops:


for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
   }
for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
   }

The Time Complexity of above two loops will be logC(n).

2. Time Complexity of a loop is considered as O(loglogn) if the loop variable is reduced/increased exponentially by a constant 
amount.



// Here c is a constant greater than 1   
   for (int i = 2; i <=n; i = pow(i, c)) { 
       // some O(1) expressions
   }




Comments

Post a Comment

Popular posts from this blog

Worst, Average and Best Case Analysis of Algorithms

Image
Introduction:  We all understand that as the input size (n) grows, an algorithm's running time grows. Even though the input is the same size, running times can change between distinct input instances. We then conduct best, average, and worst-case analyses in that situation. In this post, we will take an example of Linear Search and will analyze its best, average, and worst-case time complexity. Consider the linear search example where we look for an item in an array. In Linear search, we simply traverse the list completely and match each element of the list with the item whose location is to be found. If the match is found, then the location of the item is returned; otherwise, the algorithm returns -1. The steps used in the implementation of Linear Search are listed as follows - First, we have to traverse the array of elements using a for a loop. In each iteration of for loop, compa...
Read more

Asymptotic Analysis

Introduction: If you want to analyze two algorithms how you will measure them- The simplest way to do it is to implement both the algorithms run them on some machine and check which one is faster. But there are so some problems associated with this approach:        For some input algorithm A may perform well and for some input algorithm B may perform well.     For some input algorithm  A,  is performing good on machine X but for the same input on machine Y algorithm B is doing good All such problems can be handled using the asymptotic notation as in asymptotic notation the performance of the algorithm is measured in terms of input size. How the performance of algorithms grows as the input size grows. The machine-dependent constants can always be ignored after a certain value of input size.   Does it always work? Asymptotic notation does not do good always for example .      Two algorithms with the sa...
Read more