-3

I am a newbie to algorithms. One thing that i always get confused is about calculation of algorithm runtimes. For example: The following piece of code in Python

for i in range(n):
    #O(?)
    i*=k

What is the runtime of the above for loop? The answer that has been provided to me is: O(log n to the base k).

I am finding it difficult to understand as to how this runtime was arrived at.

Any hep would be very much appreciated.

Kiran Hegde
  • 95
  • 1
  • 2
    It's pretty obvious that that runtime cannot possibly be correct. The loop body is executed n times, and every time it is doing work, so clearly it *must* be *more than* O(n). – Jörg W Mittag Sep 26 '18 at 17:42
  • The other problem with the provided answer is that O() notation ignores constant factors, so the base for the logarithm doesn't matter. It should be O(log n), except that, as @JörgWMittag said, if you're doing anything n times then the complexity can't be smaller than O(n). – David Thornley Sep 26 '18 at 18:15
  • @DavidThornley: Well, you can certainly be more precise. There's nothing wrong with O(log_k n), it's just that O(log_k n) == O(log_10 n) == O(log_2 n) == O(log n) == O(23 log_42 n + 85). – Jörg W Mittag Sep 26 '18 at 18:18

1 Answers1

0

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.

When n is 20 and k is 3, how much is log( n, k )? It should be log( 20, 3 ) which is about 2.72.

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.

BobDalgleish
  • 4,644
  • 5
  • 18
  • 23
  • 1
    `i` is *not* the iteration control variable. It is the element variable. `for`/`in` in Python is a `foreach` iterator, not a C-style `for` (which is essentially a `while`) loop. There will always be `n` iterations of the loop, no matter what you do to `i`. When `n` is `20` and `k` is `3`, there should be 20 iterations of the loop, each with a multiplication which takes log(i) time (i.e. number of digits / bits). I believe, there are actually faster multiplication algorithms, but I don't think Python is using them. The lower bound for multiplication is still unknown. – Jörg W Mittag Sep 26 '18 at 17:56
  • The runtime is circa SUM(log i, from 1 to n), which is more than n and less than n * log n. – Jörg W Mittag Sep 26 '18 at 18:01
  • Sorry, that should be SUM((log i)^2, from 1 to n), of course, which is more than n and less than n * (log n)^2. – Jörg W Mittag Sep 26 '18 at 18:16