1

I need to calculate the time complexity of the following loop:

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

 statements;

}

Assuming n = 10, Is i < n; control statement going to run for n time and i++; statement for n-1 times? And knowing that i = 1; statement is going to run for a unit of time.

Calculating the total time complexity of the three statements in for-loop yields 1+n+n-1 = 2n and the loop with its statements yields 2n+n-1 = 3n-1 = O(n).

Are my calculations correct to this point?

Shadab
  • 21
  • 1
  • 5
  • 1
    The time complexity of this loop is `O(n)` if the time complexity of inner statements does not depend on `n`. – DAle Feb 12 '19 at 14:15
  • Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Heretic Monkey Feb 12 '19 at 14:19

1 Answers1

0

Yes, your calculations are correct, a for loop like such would have O(n) notation.

Similarly, you could make a calculation like such:

for(int i = 0; i <n*2; i++){
//calculations
}

in this case, the for loop would have a big O notation of O(n^2) (you get the idea)

This loop takes O(n^2) time; math function = n^n This way you can calculate how long your loop need for n 10 or 100 or 1000

This way you can build graphs for loops and such.

as DAle mentioned in the comments the big O notation is not affected by calculations within the loop, only the loop itself.

Kristoffer Tølbøll
  • 3,157
  • 5
  • 34
  • 69