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 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.
-
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)$ 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 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}{1-x}$$ Notice how all the closed-form equations have constant terms?
-
amWhy over 6 yearsJust 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 yearsTo 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 yearsThanks for the lesson! :-)