Why Is The Manual Summation Of An n log n Equation Not Equal To The Programmatic Summation Of An θ(n log n) for Loop?

1,962

The notation $\sum_{i=1}^{\log n}$ confuses you. The outer loop in the first example executes with indices $2^k$, where $k \in [0, n]$. Number of executions of such a loop will be $log(n) + 1$, but not $log(n)$.

Of course, asymptotic time complexity of this piece of code will still be $\Theta(n \log n)$.

Share:
1,962

Related videos on Youtube

algoHolic
Author by

algoHolic

The first step is to admit, "I have a Halting problem!"

Updated on August 01, 2022

Comments

  • algoHolic
    algoHolic 11 months

    There is an algorithm text book that I'm reading to teach myself asymptotic analysis. To demonstrate that not all two-level nested for loops are $\Theta(n^2)$, the book presents the following code to be analyzed...

    /* θ(n log n) */
    sum = 0;
    for(int i = 1; i <=n; i*= 2)
        for(int j = 1; j <=n; j++)
            sum++;
    

    The book calculated that the running-time of the above implementation would be $\Theta(n \log n)$. The book arrived at the $\Theta(n \log n)$ running-time, after first suggesting that the intermediate Sigma notation is $\sum_{i=1}^{\log n} n = n \log n$.

    Before I ask my question, I'll first set up the context of my question by showing another block of code with $\Theta(n^2)$ running-time — whose corresponding Sigma notation is $\sum_{i=1}^{n} i = \frac{n(n-1)}{2}$...

    /* θ(n^2) */ 
    sum = 0;
    for(int i = 0; i <=n-1; i++)
        for(int j = n-1; j > i; j--)
            sum++;
    

    If the above-listed $\Theta(n^2)$ code were run with $n = 8$, then the value of the variable sum, would end up being 36. Correspondingly, the manual calculation of the $\Theta(n^2)$ closed-form summation equation ($\frac{n(n-1)}{2}$) would work out to be 36 if you were to plug the value 8 into its $n$.

    If — on the other hand — the above listed $\Theta(n \log n)$ code were run with $n = 8$, then the value of its sum variable would end up being 32. However, the manual calculation of $\Theta(n \log n)$ — where $n = 8$ — would work out to be 24. Because asymptotic analysis always assumes $log_2$, then $\log 8 = 3$. And $8 \cdot 3 = 24$.

    So now, here are my questions:

    1. How come the $\Theta(n^2)$ code's summation and the summation of its corresponding Sigma notation's closed form equation both work out to be 36 — but the $\Theta(n \log n)$ Sigma notation equation calculation does not jibe with the value calculated by the corresponding $\Theta(n \log n)$ code listed above?

    2. What is the relationship between the 24 that comes out of the $\Theta(n \log n)$ Sigma notation equation calculation and the corresponding code listed above?

    3. What would I need to change in the above-listed $\Theta(n \log n)$ code, to make the final value of the summation, equal to the summation calculated in its corresponding Sigma notation equation?

    4. What would the the $\Theta(n \log n)$ Sigma's closed-form equation ($n \log n$) look like fully expanded — where $n = 8$?

    Thank you in advance for your answers.


    EDIT: Please, don't let my use of MathJax fool you into thinking I'm some kind of Math dude. 'Coz I'm not. I suck at Math. Which is the very reason why I couldn't answer the question on my own. I also suck at Math jargon. Therefore, I would not be offended in the least if any answers and comments used ELI5-level plain English. In fact, I'm gonna have to insist on jargon-less, ELI5-level plain English. Please? Thanks.

  • algoHolic
    algoHolic over 6 years
    Which one of the four (count 'em) questions in my OP — five counting the one in the title — confuses you? Because you've addressed neither of them.
  • HEKTO
    HEKTO over 6 years
    @algoHolic - $n \cdot (\log(n) + 1)$ with $n=8$ will give you 32. And please be creative, but not aggressive
  • algoHolic
    algoHolic over 6 years
    I wasn't being creative. I was being repetitive. Meaning: I only repeated your own usage of "confused", @HEKTO. Nor was I being "creative" with the $\sum_{i=1}^{\log n} n = n \log n$ Sigma notation. Like I've already said in my OP — I'm only repeating the Sigma notation that I copied from an algorithm analysis text book I'm reading. Like I also said — The book based its $\Theta(n \log n)$ running-time solution on what the book claims was the summation of the closed-form of the $\sum_{i=1}^{\log n} n = n \log n$ Sigma notation that the book presented to support its solution...
  • algoHolic
    algoHolic over 6 years
    ...There are dozens of algorithm-related, Sigma notated summations that contain constant terms in their closed-form equations. The above-mentioned $\sum_{i=1}^{n} i = \frac{n(n-1)}{2}$ is one example. So, as a naive self-learner, I gotta figure that the author intentionally presented his $\sum_{i=1}^{\log n} n = n \log n$ summation for some specific reason. Which begs the question: What IS the reason the author uses $\sum_{i=1}^{\log n} n = n \log n$ to represent the summation of the above $\Theta(n \log n)$ code? — (that I copy/pasta-ed from the book, I hasten to repeat)...
  • algoHolic
    algoHolic over 6 years
    ...If $\sum_{i=1}^{\log n} n = n \log(n) + 1$ was indeed what the author intended, there is no obvious reason why he would not have just tacked the stupid $+ 1$ onto the end of his equation. After all, by that point in the book, he'd already drilled the universally parotted, "Big-O ignores constants and low-order terms" dogma into the reader. So it would have been abundantly clear to me how to deal with the $+ 1$ term in the Sigma notation, if he hadda included it. Granted — maybe the author himself is confused.
  • algoHolic
    algoHolic over 6 years
    I didn't create these either. Cormen, et. al did... $$\sum_{k=0}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$ $$\sum_{k=0}^n k^3 = \frac{n^2(n+1)^2}{4}$$ $$\sum_{k=0}^{n} x^k = \frac{x^{n+1} - 1}{x - 1}$$ $$\sum_{k=0}^\infty x^k = \frac{1}{1-x}$$ Notice how all the closed-form equations have constant terms?
  • amWhy
    amWhy over 6 years
    Just curious: I am clueless as to what "ELI5-level" means. Seriously. I'm from the US, so I'm guessing it relates to a specific level (grade-level) of mathematics. But if you could be so kind as to educate my guesses, I'd be much obliged.
  • algoHolic
    algoHolic over 6 years
    To answer your Q @amWhy : "•E is for Explain - merely answering a question is not enough" | "•LI5 means friendly, simplified and layman-accessible explanations - not responses aimed at literal five-year-olds" | [Source] | It comes from an old adage (and I paraphrase) — "If you can't explain something simple and straightforward enough so that a ten year old would understand it — then you really don't understand that something yourself"...
  • amWhy
    amWhy over 6 years
    Thanks for the lesson! :-)