0

I understand that the upper bound (i.e. for (int i = 0; i < n; i++) for a non-nested/single for loop is the worst case time complexity. Basically, n is the maximum number of times the for loop will iterate. With this piece of information in mind, here is pseudo code that I have written.

for (i = 1; i <= n; i++)
   for (j = n; j >= 1; j--)
      cout << "hi";

From this piece of code, it's obvious that the time complexity for the upper bound of the outer for loop is O(n).

However, what would the time complexity for the inner for loop be?

Some programmer dude
  • 400,186
  • 35
  • 402
  • 621
Paul Lee
  • 119
  • 3
  • 2
    `O(n)`, since you start from `j` equal `n` and stop at `j` equal `0`. The outer loop is in `O(n^2)`, because it repeats `n` times a loop in `O(n)`. – Patrick Trentin Sep 16 '17 at 21:37
  • The complexity of `cout<<"hi"` when repeated is unspecified, and can vary between implementations (e.g. sensitivity to strategies for buffering and flushing of the buffers). – Peter Sep 16 '17 at 23:24

3 Answers3

1

The statement in the inner loop gets executed n*n times what results in the complexity of O(n^2).

Ardavel
  • 1,445
  • 1
  • 12
  • 23
1
for (i = 1; i <= n; i++)//                 O(n)
   for (j = n; j >= 1; j--)//              O(n)
      cout << "hi";//                      O(1)

Total: O(n)*O(n)*O(1)=O(n^2)

0

for (j = n; j >= 1; j--) and for(j = 0; j <= n; j++) are equivalent statements as far as how many times they will be executed, one just counts from the upper bound to 0 and the other counts from zero to the upper bound

Mitch
  • 3,342
  • 2
  • 21
  • 31