# 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 Author by

### algoHolic

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

Updated on August 01, 2022

• 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$?

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 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 over 6 years
@algoHolic - $n \cdot (\log(n) + 1)$ with $n=8$ will give you 32. And please be creative, but not aggressive
• 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 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 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 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 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 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 over 6 years
Thanks for the lesson! :-)