Determine the number of basic steps required in the following algorithms in big-oh notation

The book doesn't quite explain how to do this. I tried looking at the notes my teacher gave me, but it's an easier problem than what the book shows. I've been staring at the book for about an hour trying to figure out this problem, but I still can't think of anything. If I can figure this one out, I can do the rest of the problems.

Here is what the book has:

procedure b(n: positive integers)
x <- 0
i <- n
while i >= 1 do
begin
i <- i/3
x <- x+1
end
return(x)


Books answer: $$O(\log_3 n) = O(\log n)$$, where does the $$\log$$ part come from?

1 Answer

Note that each iteration of the loop takes a constant number of operations. Therefore, the order of the algorithm is the order of the number of iterations through the loop.

Each iteration divides $$i$$ by $$3$$, starting with $$n$$, until $$i < 1$$ happens, at which point the loop terminates. So you are really asking, given a number $$n$$, how many times can I divide it by $$3$$ to get something under $$1$$.

Equivalently, you need to find minimum integer $$k$$ where $$3^k \ge n \iff k \ge \log_3 n$$

• So what shows that it would be log n? Commented Feb 21, 2019 at 1:43
• @ChrisD93 it will take you $O(k) = O(\log_3 n) = O(\log n)$ iterations to get through the loop -- as my argument demonstrates. What is it that you specifically have a question about? Commented Feb 21, 2019 at 12:48
• Sorry for the delayed response. Anyway, my question is that I still don't understand how i/3 becomes logn Commented Feb 24, 2019 at 19:29
• @ChrisD93 $k=\log_3 n$ by definition is the solution of the equation $3^k=n$. Commented Feb 24, 2019 at 20:39