0
$\begingroup$

Below is a problem I made up and my solution to it.

Problem:
Given the following recurrence relationship, find $\Theta(T(n))$. $$ T(n) = T\left( \dfrac{n}{2}\right) + n^2 $$

Answer:
To solve this problem, I use the Master's Theorem. I am using this link as reference:
Wikipedia Article
\begin{align*} a &= 1 \\ b &= 2 \\ c_{crit} &= \log_2 1 = 0 \\ \end{align*} This means we are in case 3. Hence the answer is: $$ T(n) = \Theta(n^2) $$

I am concerned my answer is wrong because we have: $$ T(n^2) = n^2 + (\dfrac{n}{2})^2 + (\dfrac{n}{4})^4 + ... 1 $$ Here we have $O(\log n)$ terms. Hence, I was thinking the answer might be: $$T(n) = \Theta ( \log(n) n^2 ) $$ I do believe that: $$T(n) = O( \log(n) n^2 ) $$ That is $\log(n) n^2$ represents an upper bound on $T(n)$.

$\endgroup$
3
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Commented Apr 3, 2022 at 1:25
  • $\begingroup$ See cs.stackexchange.com/questions/138406/… for similar feedback on a prior question. $\endgroup$
    – D.W.
    Commented Apr 3, 2022 at 1:27
  • $\begingroup$ @D.W. I posted why I think my answer might be wrong. $\endgroup$
    – Bob
    Commented Apr 3, 2022 at 2:47

2 Answers 2

1
$\begingroup$

$$\begin{align} T(n) &=& n^2 + \left(\frac{n}2\right)^2 + \left(\frac{n}4\right)^2 + … \\ & = & n^2 \left(1+\frac14 + \frac1{16} + …\right)\,\,\,\,\\ &\leqslant& n^2\sum\limits_{k=0}^{+\infty}\frac1{4^k} =\frac{4n^2}{3}\,\,\,\,\,\,\,\,\,\,\,\,\, \end{align}$$

There is no problem here: even if there are $\mathcal{O}(\log n)$ terms, those terms are smaller and smaller.

$\endgroup$
1
  • 1
    $\begingroup$ Yeah, to point to the place of confusion, Bob had term (n/4)^4 instead of (n/4)^2 and that lead him astray I think. $\endgroup$ Commented Apr 3, 2022 at 9:07
0
$\begingroup$

You are right that there are on the order of $\log n$ terms in the sum and that each term is $n^2$ times a constant; however, the upper bound $O(n \log n)$ thus obtained, while correct, is not asymptotically tight because the coefficients decrease at a geometric rate and sum to at most some fixed constant $c$. More specifically, the coefficients are $1, 1/4, (1/4)^2$, etc, and the sum of these constants is at most $2$. So, the total cost might be more than $n^2$, but the total cost is still at most $2n^2$, and the constant $2$ is subsumed in asymptotical notation.

More generally, if the common ratio $0 < r < 1$ in a geometric progression is less than $1$, then $1+r+r^2+\cdots+r^{\log_2 n} = \Theta(1)$. This is why, in this case of the Master theorem, the total cost of all levels of the recursion tree is dominated by the top level of the recursion tree, i.e. the constant $1$ In the sum $1+r+r^2+\cdots+r^{\log_2 n}$ dominates the sum (by up to a constant factor).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.