+2 votes

What is the time complexity of the following loop?

double j = 1.0
while (j < log n) {
    j = 1.3 * j
}

The loop, if it was j < n, then it would be log n. However, it goes from j = 1 to log n instead of n. How do you combine that to find the total complexity?

in Asymptotic Analysis by AlgoStar (416 points)

1 Answer

+2 votes
 
Best answer

So let's say there are k steps taken in the program.

1.3^k = log n

k = log1.3log n

Time complexity is O(loglog n).

by AlgoMeister (768 points)
selected by
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...