CODEWITHSUNDEEP
algorithmcomplexity-theorydiscrete-mathematicsbig-o
Miku
Miku

Reputation: 41

Analyzing runtime of function

Click here to check question image

Hello, I got this question, but got wrong on its answer that was about analyzing runtime of function.

From my perspective, outer while loop runs for n^2 times. Specifically it starts from 1 to n^2, thus, runtime is "n^2 - 1", then we call it just O(n^2) for simplicity.

And inner for loop runs for logn (base 2) times because division by 2.

Since it is nested loop, we have to multiply those 2 runtimes.

So whole runtime become O(n^2 * logn), however, my answer is wrong according to answer.

Can you explain the reason why answer is not O(n^2 * logn) but O(n^2)?

Upvotes: 1

Views: 87

Answers (1)

user1196549
user1196549

Reputation:

The inner loop is never executed because n²<1 is false, hence the while loop is executed (n²-1)/2 times.

Upvotes: 2

Related Questions