CODEWITHSUNDEEP
algorithmbig-otime-complexity
Thomas Ball
Thomas Ball

Reputation: 153

What would the big O notation for this function?

What would be the worst time complexity big O notation for the following pseudocode? (assuming the function call is an O(1)) I'm very new to big O notation so I'm unsure of an answer but I was thinking O(log(n)) because the while loop parameters multiplied by 2 each time or would that just be O(loglog(n))? Or am I wrong on both counts? Any input/help is appreciated, I'm trying to grasp the concept of big O notation for worst time complexity which I just started learning. Thanks! 

i ← 1
while(i<n)
    doSomething(...)
    i ← i * 2
done

Upvotes: 2

Views: 498

Answers (3)

dth
dth

Reputation: 2337

O(log(n)) is correct when you want to state the time complexity of that algorithm in terms of the number n. However in computer science complexity is often stated in the size of the input, i.e. the number of bits. Then your algorithm would be linear, i.e. in O(k) where k is the input size.

Typically, other operations like addition are also said to be linear not logarithmic. A logarithmic complexity usually means that an algorithm does not have to consider the complete input. (E.g. binary search).

If this is part of an exercise or you want to discuss complexity of algorithms in a computer science context this difference is important.

Also, if one would want to be really pedantic: comparison on large integers is not a constant time operation, and if you are considering the usual integer types, the algorithm is basically constant time as it only needs up to 32 or 64 iterations.

Upvotes: 3

Chad S.
Chad S.

Reputation: 6633

If i is doubling every time, then the number of times the loop will execute is the number of times you can double i before reaching n. Or to write it mathematically, if x is the number of times the loop will execute we have 2^x <= n. Solving for x gives x <= log_2(n). Therefore the number of times the loop will execute is O(log(n))

Upvotes: 7

Severin Pappadeux
Severin Pappadeux

Reputation: 20080

i is growing exponentially, thus loop will be done in logarithmic time, O(log(n))

Upvotes: 5

Related Questions