CODEWITHSUNDEEP
big-otime-complexity
user3011240
user3011240

Reputation: 97

What is the running time of the following code?

Isn't the running time simply n-i, which is just O(n)? Or am I not considering everything in this situation? 

i <- c
while i < n do
i <- i*c
end while

Upvotes: 1

Views: 391

Answers (2)

Chimba
Chimba

Reputation: 132

The running time of this algorithm is O(log n). It will not be n-i because you are not incrementing the loop counter by adding or subtracting a value. Rather you are incrementing the loop counter by c so you are scaling it up by c in every iterations. So the maximum number of iterations it can go is log_c(n).

Upvotes: 2

Maciej Asembler
Maciej Asembler

Reputation: 674

Wouldn't it be logarithm with the base of c from n ?

You are basically multiplying i until it reaches the value of n.

Upvotes: 3

Related Questions