CODEWITHSUNDEEP
c++algorithmtimetime-complexity
Toy_Soldier
Toy_Soldier

Reputation: 41

Confusion in time complexity

How would be the time complexity of below program O(n^2)?

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

The second for loop won't execute right as in the condition j <= n,the value of j will always be greater than n.
Check the 3rd point in this link

Upvotes: 0

Views: 61

Answers (2)

Hac
Hac

Reputation: 3

I think what the author actually means here is

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

In this way, the complexity is (1+n/c)*(n/2c) = O(n^2)

Upvotes: 0

Henry Garcia
Henry Garcia

Reputation: 46

In the event that n and c are positive numbers, then yes the second for loop won't execute.

It appears to me that those for loops were written incorrectly in that link.

Upvotes: 1

Related Questions