2

He is recurrence relation and my solution:

$$ \begin{align} T(n) & = T(n/2) + O(n) \\[6pt] & = T(n/4) + \frac{cn}{2} + cn \\[6pt] & = T(n/8) + \frac{cn}{4}+ \frac{cn}{2} + cn \\ & {}\ \ \ \vdots \\ & = \sum_{i=0}^{logn}\frac{cn}{2^i} = cn \frac{1-(1/2)^{logn+1}}{1-1/2} \end{align} $$

I am not sure if I did geometric sequence in a right way. Could you please help me to verify if my math is correct here? Thanks

UserMoon
  • 349

1 Answers1

1

The upper limit of your summation is wrong -- it whould not be $n$. How many summands do you have? (recall that you start with $n$, then have $\frac{n}{2}$, $\frac{n}{4}$, $\frac{n}{8}$, $\ldots$, and stop when reaching, say $1$. This will only change the low-order terms of your solution (roughly, $1/n$ instead of $1/2^n$ in the fraction).

Also, importantly you may want to be careful with your $O(\cdot)$ notation. Did you mean a $\Theta(\cdot)$ (as your use of a constant $c$ seem to hint)? Recall that (for instance) $1=O(n)$, which would lead to a total complexity of $T(n)=\Theta(\log n)$.

Finally, as a general tool to solve or do sanity checks on the solutions of these recurrence relations, are you familiar with the Master theorem?

Michael Hardy
  • 1
Clement C.
  • 67,323
  • yes, I know Master Theorem. But I need to be able to prove running time without using Master Theorem. I did not really understand what is the issue with my upper limit. If we assume that our n is some power of 2. Then, at some point we get 1. So our sequence is 1, 2, 4, 8, 16, ... , n . Right? Thus we run from 1 to n... am I wrong? – UserMoon Feb 15 '15 at 20:35
  • You only have $\log n$ terms, not $n$. If it's unclear, run an example with $n=4$: you have $2$ ($n/2$) then $1$ ($n/4$), and then you stop as you reached 1. (for instance, if the upper bound in your sum were $n$ instead of $\log n$, the last term would be $\frac{cn}{2^n}$ instead of $\frac{cn}{2^{\log n}}=c$). – Clement C. Feb 15 '15 at 20:37
  • Thank you! Can you check my edited summation? Is it correct now? I am not sure if I express geometric series in a right way – UserMoon Feb 15 '15 at 20:47
  • Given the summation on the right, the expression you get is correct. Note that you can simplify further: $2^{\log n +1} = 2n$, and $\frac{1}{1-\frac12}=2$. – Clement C. Feb 15 '15 at 20:53