CODEWITHSUNDEEP
time-complexity
tejartr445
tejartr445

Reputation: 1

time complexity of the given code and the reason

enter image description here

can any one tell me why is the time complexity O(n) while the outer loop runs for log(n) and inner loop runs for n time the time complexity should be O(n*log(n)) but its O(n)?

Upvotes: 0

Views: 26

Answers (1)

Berthur
Berthur

Reputation: 4495

The inner loop doesn't run n times, it runs i times. i varies in the outer loop. So to find the time complexity, you set up an expression for how many times the inner loop runs. In your image, this is already done in the explanation.

From there, after some mathematics, you will find that the time complexity is O(n). Hint: Geometric series.

Upvotes: 0

Related Questions