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

Question

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?

Answer 1

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 $$