The runtime of an algorithm is often expressed as a function of its complexity. In your example, you can think of "runtime" as "the number of steps". The complexity is
O( log( n, k ) ), according to your source.
3, how much is
log( n, k )? It should be
log( 20, 3 ) which is about
How many steps does your algorithm take? If you print out your values on each loop you should see something like:
i = 0, i*k = 0
i = 1, i*k = 3
i = 4, i*k = 12
i = 13, i*k = 39
So, it took four steps to perform the algorithm. Clearly there is a disagreement between 3 (rounded up from 2.72) and 4.
Looking at your statement of the algorithm, I suspect that the Python code should have been stated as follows:
k = 3
n = 20
i = 1
while i <= n:
print "i =", i, "i*k =", i*k
i = i*k
i = i+1
This algorithm will show only three steps, matching the estimated complexity.
You should note that your original statement of the Python code is wrong because it is modifying the iteration control variable,
i, in the middle of the loop. Such practices will lead to confusion and errors and are strongly discouraged.