5
$\begingroup$

I'm currently in a course, and I for the life of me cannot figure out what my professor is doing. I could really use a working example, and I was hoping someone here might oblige.

Suppose we have this recurrence:

$$ T(n) = 2T(n/2) + \log n$$

How would we figure out running time for this, and specifically, how would we PROVE the upper and lower bounds (ideally as tight as possible)?

I tried working through my homework with the help of a few YouTube videos, but I don't seem to be following it. In giving an explanation, please try and be careful to explain why something is a certain time, as I haven't really gotten the hang of intuiting that yet.

I have some working knowledge of induction and calculus, but it seems like I'm missing a big chunk of context somewhere and I really need to get up to speed. Thank you for any assistance.

Improve this question
$\endgroup$
1
  • $\begingroup$ "How would we figure out running time for this?" Note that it doesn't have a running time: it's a mathematical function. It may be that, in your case, the function measures the running time of something but the function itself doesn't run. (Similarly, a number might represent a price or a length but we don't say "What is the cost of $3+8$?" or "What is the length of $\tfrac12\times47$?") $\endgroup$
    – David Richerby
    Commented Feb 12, 2017 at 23:59

2 Answers 2

Reset to default
6
$\begingroup$

First of all, a recurrence is not necessarily about the running time of anything. So you don't figure out "the running time", you solve the recurrence.

Second, your recurrence only possibly makes sense for powers of 2, and even then, it needs a base case. I'll assume that $T(1) = C$.

You can use the master theorem to solve your recurrence, but you can also do it directly. First you expand it (for simplicity, I'm assuming the base of the logarithm is 2): $$ \begin{align*} T(2^k) &= k + 2T(2^{k-1}) \\ &= k + 2(k-1) + 4T(2^{k-2}) \\ &= k + 2(k-1) + 4(k-2) + \cdots + 2^{k-1}(k-(k-1)) + 2^k T(1) \\ &= (1+2+\cdots+2^{k-1})+(1+2+\cdots+2^{k-2})+\cdots+(1) + 2^k C \\ &= (2^k-1)+(2^{k-1}-1)+\cdots+(2-1)+(1-1) + 2^kC \\ &= (2^k+\cdots+1)-(k+1) + 2^kC \\ &= 2^{k+1}-k-2 + 2^kC. \end{align*} $$ If you want to be very pedantic, you can prove this by induction. In terms of $n=2^k$, this reads $$ T(n) = (2+C)n-\log n - 2 \sim (2+C) n. $$ In particular, $T(n) = \Theta(n)$. You could also get this conclusion from case 1 of the master theorem.

Improve this answer
$\endgroup$
7
  • $\begingroup$ How do we figure out 2^K is implicit? My instructor went through this very quickly. $\endgroup$
    – s_werbermanjensen
    Commented Feb 12, 2017 at 21:02
  • 1
    $\begingroup$ In your context, functions like $T(n)$ are only defined for positive integers. You can only divide a positive integer by 2 if it is even. Assuming a unique base case at 1, the only integers which reach 1 upon repeated division by 2 are powers of 2. $\endgroup$
    – Yuval Filmus
    Commented Feb 12, 2017 at 21:03
  • $\begingroup$ One other question, how would we prove a lower bound? The problem I'm solving just gives us T(n) as above and says to prove upper and lower bounds (as tight as possible). $\endgroup$
    – s_werbermanjensen
    Commented Feb 12, 2017 at 22:47
  • $\begingroup$ I gave you an exact value. In particular, it's both an upper bound and a lower bound. $\endgroup$
    – Yuval Filmus
    Commented Feb 12, 2017 at 22:49
  • $\begingroup$ Ok, sorry. I wish mathematics wasn't such a deficit for me. It'd really make life easier. One other question... how would this change if it was T(n/3)? $\endgroup$
    – s_werbermanjensen
    Commented Feb 12, 2017 at 22:58
1
$\begingroup$

It's probably easier solving this using the Master Theorem.

T ( n ) = 2 T ( n / 2 ) + log ⁡ n


enter image description here

So in this case A=2, B=2, and D=0 because f(n) = log n and n^0 * log n = log n

We of course assume the base case is a constant such that T(1) = C

So we can easily see that the answer for this is T ( n ) = Θ ( n ) , since A is greater than B to the power of D.

We can see that is true just by plugging in the values

= A > B^D

= 2 > 2^0

= 2 > 1 (which is always true)

This guy on YouTube has a very nice video explaining how to solve recurrences using the Master theorem, I will leave the link here.

Improve this answer
$\endgroup$

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