1

I have a recurrence as follows: \begin{equation} T(n) = \begin{cases}a, & \text{for $n=1$}\\ T(\dfrac{n}{2})+b,&\text{for $n\geq2$} \end{cases} \end{equation} $a$ and $b$ are some undefined constant.

I'm asked to find an explicit formula using substitution, showing my work for $k$ iterations. I understand, conceptually, how to substitute: \begin{align*} T(n) &= T(n/2)+b\\ T(n/2) &= T(n/4) + 2b\\ T(n/4) &= T(n/8) + 3b\\ T(n/8) &= T(n/16) + 4b \end{align*}

WolframAlpha tells me that this recurrence resolves to $T(n) = a + \dfrac{b \log(n)}{\log(2)}$, but I have no idea how it arrived there, or if that is even correct.

What is the correct way to perform this substitution to arrive at an explicit formula?

Justin
  • 15

2 Answers2

0

First, one can notice that this recurrence is defined only for numbers $n$ which are powers of 2.

To solve the recurrence, you can try to unravel it.

Namely, $$T(n) = b+T\left(\frac{n}{2}\right) = b+b+T\left(\frac{n}{4}\right)= b+b+b+T\left(\frac{n}{8}\right) = 3b+T\left(\frac{n}{2^3}\right)$$

We can see that the coefficient next to $b$ increases by one in every step and that the argument of $T$ gets divided by two every time. So, we can infer that the general formula would be: $$T(n) = k\cdot b + T\left(\frac{n}{2^k}\right)$$ for some $k\in\mathbb N$.

But, we are aiming to get $n=2^k$, in order for the chain to terminate. This gives us that $k=\log_2 n$.

Now we have $$T(n) = b\log_2 n + T(1) = b\log_2 n+a$$

You can use mathematical induction to prove that this is indeed the general formula for $T(n)$.

Also, this formula is equivalent to the formula WolframAlpha gave.

Haris Gušić
  • 4,217
  • Thanks Haris, that's helpful. I understand that your formula and the WolframAlpha formula are the same--just different bases. The bit that I don't 100% understand is "But, we are aiming to get $n=2k$, in order for the chain to terminate. This gives us that $k=\log_2 n$." – Justin Feb 21 '19 at 23:13
  • @Justin We have $T(n/2^k)$ in the formula. We can express $T(n/2^k)$ in terms of $T(n/2^{k+1})$ and so on. But we want this formula to end somewhere. Since the recursive formula for $T$ defines $T(1)=a$, we want to get $T(1)$ in the formula. To do that, we need $n/2^k=1$, i.e. $n=2^k$. The solution of this equation is $k=\log_2 n$. Does this clear it up? – Haris Gušić Feb 21 '19 at 23:18
  • I understand why we want to get to $n=2^k$, I just don't understand how/why $n=2^k$ means $k=\log_2n$. I think this might be some basic principle of mathematics that I don't know. – Justin Feb 21 '19 at 23:20
  • @Justin This is called the logarithm of a number. Saying $k=\log_2 n$ means that we need to raise $2$ to the power of $k$ to get the number $n$. This is just the definition of a logarithm. – Haris Gušić Feb 21 '19 at 23:25
  • 1
    Ah, got it. I haven't taken any math classes above Algebra II, and that was maybe 20 years ago. Cheers. – Justin Feb 21 '19 at 23:29
0

It might be useful to rewrite the recursion as follows:

  • $\boxed{n=2^k} \Rightarrow \boxed{t_k = T(2^k)}$
  • $\Rightarrow \boxed{t_{k+1} = t_k + b, t_0 = a}$ for $k \in \mathbb{N}$
  • Telescoping gives $\boxed{t_k} = t_0 + \sum_{i=0}^{k-1} (t_{i+1} - t_i) \boxed{= a + kb}$
  • Having in mind that $n=2^k \Leftrightarrow k = \log_2 n = \frac{\ln n}{\ln 2}$ you get: $$\boxed{T(n) = a+ b\cdot \log_2 n} \mbox{ for } n= 2^k, k \in \mathbb{N}$$
trancelocation
  • 32,243