4

I'm having trouble analyzing the following for loop algorithm:

for (int i = 1; i < n; i = i * C)
    for (int j = 0; j < i; j++)
        Sum[i] += j * Sum[i];

I know that the first line has a complexity of O(logn) (as long as C > 1), but what has me stumped is the second line. I believe I understand the basics of what is happening with it:

For example,

if n=20, the inner loop will do 1+2+4+8+16 "work".

But I don't know how to write that out. I'm nearly sure the total work done altogether in the loops is O(n), and that the first line is O(logn), but how do I more concretely specify what the middle line does?

NuclearFish
  • 69
  • 1
  • 4

2 Answers2

3

i will have values of a form:

C^0, C^1, C^2, ...., C^ log_c(n)

Hence the inner loop will run C^0 + C^1 + C^2 + ... + C^log_c(n) times. This is a geometric series which sum up to:

enter image description here

So substiture r with C, n with log_c(n) we get:

(1-C^log_c(n)) / (1-C) = (1-n)/(1-C), which is positive for any C > 1 and proportional to n. Hence the complexity is O(n) indeed.

(The formula image is taken from Wikipedia )

user2736738
  • 30,591
  • 5
  • 42
  • 56
Eugene Sh.
  • 17,802
  • 8
  • 40
  • 61
  • If `n` is not a power of `C`, then `log_C(n)` isn't even an integer, so `i` wont take value `C^log_C(n)`. If `n` is the `p`-th power of `C` (that is: `n = C^p`), then the for-loop will stop at `C^{p-1}`, because there is a `<`, not a `<=`. I've written out a somewhat more pedantic version of the same argument, just in case someone is interested. :] – Andrey Tyukin Jan 26 '18 at 18:32
  • @AndreyTyukin I agree that the calculation is not the most pedantic one, but it is sufficient for big-o reasoning. It's good to have other approaches too. – Eugene Sh. Jan 26 '18 at 18:36
  • Well, yes. But there is also the danger that one drops some factors too quickly, and then ends up with `C^(HIDDEN_FACTOR * log(n))` (polynomial) instead of `HIDDEN_FACTOR * n` (linear). In your calculation above, you drop the factor `C` right away (that's approximately the factor between `C^p + 1` and `C^{p+1}`). It turns out to be ok in this case. But in another case, where the total effort is something like `2^{C n}` instead of `2^n`, that would make a big difference. – Andrey Tyukin Jan 26 '18 at 19:54
0

I'll use the latex-esque notation sum_{k=a}^b f(i) to denote the sum f(a) + f(a + 1) + ... + f(b), and I will write a^b to denote a raised to the b-th power.

First, find the positive integer p such that C^p < n <= C^{p+1} holds, this is the number of iterations in the outer loop. Now, the outer loop variable i takes values 1, C, C^2, C^3, ..., C^p, that is, C^k for k=0, ..., p. It is obvious that for each k, the inner loop needs i = C^k time steps. Thus, the total effort T (measured in the number of innermost instructions) is:

T = C^0 + C^1 + ... + C^p = sum_{k=0}^p C^k = (C^{p + 1} - 1) / (C - 1)

This is the geometric series. Now, taking the logarithm of the assumption about p, we get:

p < log_C(n) <= p+1

or, rewritten such that p is in the middle:

log_C(n) - 1 <= p < log_C(n)

Now substitute all three formulas into the formula of the monotonically increasing function x -> (C^{x + 1} - 1) / (C - 1):

(n - 1) / (c - 1) <= (C^{p + 1} - 1) / (C - 1) = T < (Cn - 1) / (c - 1)

Now T is bounded by two O(n) (or rather Theta(n)) terms from both sides. Thus, it must itself be O(n) (or, again, Theta(n), meaning that the effort is at most linear, and no tighter upper bound exists).

Andrey Tyukin
  • 43,673
  • 4
  • 57
  • 93