5

I'm having trouble understanding how to make this into a formula.

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j += i) {

I realize what happens, for every i++ you have 1 level of multiplication less of j.

i = 1, you get j = 1, 2, 3, ..., 100

i = 2, you get j = 1, 3, 5, ..., 100

I'm not sure how to think this in terms of Big-theta.

The total of j is N, N/2, N/3, N/4..., N/N (My conclusion)

How would be best to try and think this as a function of N?

Mappan
  • 2,537
  • 2
  • 22
  • 27
  • 3
    So your question can be actually reduced to "What is the tight bound for the harmonic series 1/1 + 1/2 + 1/3 + ... + 1/N?" For which the answer is `log N` (you can consider it as continuous sum instead of discrete, and notice that the integral of `1/N` is `log N`) – justhalf Sep 18 '13 at 03:40
  • For the second loop, pretty much. But as a whole, how the best way to think this code in terms of big-theta. That is: I'm guessing the first loop is N, and the second is the harmonic series, but I've been doing a few of these problems to get the hang of this and my math seems to always fail me. – Mappan Sep 18 '13 at 03:44
  • You seem to misunderstood something. The harmonic series (ok, multiplied by `N`) _is_ the big-theta of the whole algorithm. Note that for the second loop without the first loop, the big-theta would be fixed `N/i` – justhalf Sep 18 '13 at 03:46
  • Yes, right you are. I noticed, as you pointed out below, that the integral of 1/N = ln(N). Comparing the formula against my results gave a fairly similar lines. – Mappan Sep 18 '13 at 03:57

2 Answers2

9

So your question can be actually reduced to "What is the tight bound for the harmonic series 1/1 + 1/2 + 1/3 + ... + 1/N?" For which the answer is log N (you can consider it as continuous sum instead of discrete, and notice that the integral of 1/N is log N)

Your harmonic series is the formula of the whole algorithm (as you have correctly concluded)

So, your sum:

N + N/2 + N/3 + ... + N/N = N * (1 + 1/2 + 1/3 + ... + 1/N) = Theta(N * log N)

So the tight bound for the algorithm is N*log N

See the [rigorous] mathematical proof here (see the "Integral Test" and "Rate of Divergence" part)

justhalf
  • 8,960
  • 3
  • 47
  • 74
3

Well, you can methodically use Sigma notation:

enter image description here

Mohamed Ennahdi El Idrissi
  • 2,931
  • 2
  • 19
  • 32