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:
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)$.