CODEWITHSUNDEEP
big-odiscrete-mathematics
Alex Justiniano
Alex Justiniano

Reputation: 29

Big O notation of an algorithm

i := 1
t := 0
while i <= n:
    t := t + i
    i := 2i

So I counted the number of operations in this pseudocode as 3n+2 and after this determined that the algorithm must be O(n). I am confused about the while loop since it is less than or equal to n instead of just less than n, does this increase the number of operations?

Upvotes: 0

Views: 53

Answers (1)

CaptainForge
CaptainForge

Reputation: 1395

I counted the number of operations in this pseudocode as 3n+2

How? It should be a lot closer to O(log(n)), because at each step (except for the first step, which is passed) you're basically doing:

i := 3i

Thus, i is growing exponentially instead of linearly. Do a couple of example with n being really large (>1000) and see how quickly i can catch up.

Upvotes: 2

Related Questions