CODEWITHSUNDEEP
algorithmperformancetime-complexitycomplexity-theory
Avi
Avi

Reputation: 567

Is the running time of this algorithm log n?

I think this algorithm (or code) runs log n times because each time the amount of conditions to be evaluated decreases by a constant factor. Am I correct? If not, can you please explain to me what the running time is? 

g(x) (* x > 1 is a real number *)

while x > 1 do
   x := x/3

Upvotes: 0

Views: 70

Answers (1)

pankaj
pankaj

Reputation: 1014

let this loop runs k times , which will be the time complexity of the algorithm,
At the end of :
1st iteration :x= (x/31)
2nd iteration :x= (x/32)
3rd iteration :x= (x/33)
.
.
.
.
kth iteration: x=(x/3k) <=1 (i.e. the terminating condtion)

Solving this: taking boundary conditions:
(x/3k) =1
therefor k=Log3x
Hence the time complexity is O(LogN).
hope this helps.

Upvotes: 3

Related Questions