Why Is The Manual Summation Of An n log n Equation Not Equal To The Programmatic Summation Of An θ(n log n) for Loop? 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 &lt;=n; i*= 2)
    for(int j = 1; j &lt;=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 &lt;=n-1; i++)
    for(int j = n-1; j &gt; 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: 


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 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?
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.
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)$.
On further reading (and rereading...and rereading) of the book I referred to in my OP, it eventually registered that not only does the author write: "The first code fragment has its outer for loop executed log n + 1 times...(see pg 71)", but he also talks about a second Sigma summation function: $\sum_{i=0}^{\log n} n$,  which looks at first glance, virtually identical to the $\sum_{i=1}^{\log n} n$ summation that I originally asked about. (Notice the different values for the lower bound $i$). 

The two summation functions (see pg 30 &amp; pg 71) look so similar to my naïve mathematical eyes, that I blew off the differences between the $i=0$ and the $i=1$ lower bounds, as being just a minor typo. But on a whim, I plugged $\sum_{i=0}^{\log n} n$ into Wolfram-Alpha. And out pops...

$$\sum_{i=0}^{\log n} n = n(\log n + 1)$$

The teacher's working through a step-by-step example of the summation of a constant (starting @6.24) offers a clear, ELI5-level demonstration of expanding a summation. The key mathematical concepts to take away from that ELI5-level video, are...


when there's a constant in a Sigma notation, the index does not
affect the constant.
for a constant, $c$ and for an outer bound $n$, the closed form of
the Sigma notation, is simply expressed as, $=cn$. And most
importantly...
the closed form is evaluated only the one time; NOT $n$ times; as
one might naïvely think at first.
the "Summation Of A Constant" approach to arriving at a sum, is a general mathematical concept. As such, it is no more synonymous with the topic of computer
science, than it is with the price of tea in China.


So with that, I submit this corrected ELI5-level solution to my "fully expanded equation" question #4...

$$\log_2 8 = 3$$

$$n(\log n + 1)$$

$$= 8(3 + 1)$$

$$= 8(4)$$

$$= 32$$

I'll also take a stab at answering my own, question #1...


  How come...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?


Referring to page 71 of the above-mentioned book, the author actually says, "...the total cost for the first code fragment can be expressed as $\sum_{i=0}^{\log n} n$...". So that summation's closed-form equation — $\sum_{i=0}^{\log n} n = n(\log n + 1)$ — is what should have been used to do the summation. Not the $\sum_{i=1}^{\log n} n = n \log n$ one that I mistakenly used at first.

As the above "fully expanded equation" answer to question #4 shows, as long as you follow the "Summation Of A Constant" approach, then the value $32$ calculated by the book's $for$ loop, and the value $32$ calculated by the "fully expanded equation" answer above, actually do "jibe" — to put it in ELI5 vocab.

Having answered my own mathematics-related questions #1 and #4 to my own ELI5-level satisfaction, the other two mathematics-related questions (#2 &amp; #3) disappear by osmosis.

I am prepared to graciously defer to other more expertly-informed answers to any of the original questions. All's I ask is to ELI5 ;¬)