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
  • 380,411
  • 33
  • 383
  • 585
Paul Lee
  • 119
  • 2

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,405
  • 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,136
  • 1
  • 19
  • 28