Why Is The Manual Summation Of An n log n Equation Not Equal To The Programmatic Summation Of An θ(n log n) for Loop?
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)$.
Related videos on Youtube
algoHolic
The first step is to admit, "I have a Halting problem!"
Updated on August 01, 2022Comments

algoHolic 11 months
There is an algorithm text book that I'm reading to teach myself asymptotic analysis. To demonstrate that not all twolevel 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 runningtime of the above implementation would be $\Theta(n \log n)$. The book arrived at the $\Theta(n \log n)$ runningtime, 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)$ runningtime — whose corresponding Sigma notation is $\sum_{i=1}^{n} i = \frac{n(n1)}{2}$...
/* θ(n^2) */ sum = 0; for(int i = 0; i <=n1; i++) for(int j = n1; j > i; j) sum++;
If the abovelisted $\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)$ closedform summation equation ($\frac{n(n1)}{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:
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?
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?
What would I need to change in the abovelisted $\Theta(n \log n)$ code, to make the final value of the summation, equal to the summation calculated in its corresponding Sigma notation equation?
What would the the $\Theta(n \log n)$ Sigma's closedform 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 ELI5level plain English. In fact, I'm gonna have to insist on jargonless, ELI5level plain English. Please? Thanks.

algoHolic over 6 yearsWhich 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 yearsI 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)$ runningtime solution on what the book claims was the summation of the closedform 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 algorithmrelated, Sigma notated summations that contain constant terms in their closedform equations. The abovementioned $\sum_{i=1}^{n} i = \frac{n(n1)}{2}$ is one example. So, as a naive selflearner, 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/pastaed 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, "BigO ignores constants and loworder 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 yearsI 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}{1x}$$ Notice how all the closedform equations have constant terms?

amWhy over 6 yearsJust curious: I am clueless as to what "ELI5level" means. Seriously. I'm from the US, so I'm guessing it relates to a specific level (gradelevel) of mathematics. But if you could be so kind as to educate my guesses, I'd be much obliged.

algoHolic over 6 yearsTo answer your Q @amWhy : "•E is for Explain  merely answering a question is not enough"  "•LI5 means friendly, simplified and laymanaccessible explanations  not responses aimed at literal fiveyearolds"  [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 yearsThanks for the lesson! :)