gotchaMinor
Is there a difference between using $n$ and $\Theta(n)$ in recurrences?
Viewed 0 times
thetarecurrencesdifferencebetweenusingandthere
Problem
Is there a difference between $T(n)=2T(n/2)+n$ and $T(n)=2T(n/2)+Θ(n)$ when using the master theorem? I've seen it both ways and am a little confused. (Looking for the answer $nlogn$).
Solution
A recurrence of the form
$$
T(n) = 2T(n/2) + \Theta(n)
$$
is really a shorthand for a recurrence of the form
$$
T(n) = 2T(n/2) + f(n), \text{ where } f(n) = \Theta(n).
$$
Let us consider a recurrence of this form, and let us suppose that $an \leq f(n) \leq bn$, where $a,b > 0$. Consider the more general recurrence
$$
T_c(n) = 2T_c(n/2) + cn,
$$
with the same initial values as the $T(n)$ recurrence. You can prove by induction on $n$ that
$$
T_a(n) \leq T(n) \leq T_b(n).
$$
Therefore, if you can show that $T_c(n) = \Theta(n\log n)$ for all $c$ (where the hidden constant could depend on $c$), then it would follow that also $T(n) = \Theta(n\log n)$.
$$
T(n) = 2T(n/2) + \Theta(n)
$$
is really a shorthand for a recurrence of the form
$$
T(n) = 2T(n/2) + f(n), \text{ where } f(n) = \Theta(n).
$$
Let us consider a recurrence of this form, and let us suppose that $an \leq f(n) \leq bn$, where $a,b > 0$. Consider the more general recurrence
$$
T_c(n) = 2T_c(n/2) + cn,
$$
with the same initial values as the $T(n)$ recurrence. You can prove by induction on $n$ that
$$
T_a(n) \leq T(n) \leq T_b(n).
$$
Therefore, if you can show that $T_c(n) = \Theta(n\log n)$ for all $c$ (where the hidden constant could depend on $c$), then it would follow that also $T(n) = \Theta(n\log n)$.
Context
StackExchange Computer Science Q#97423, answer score: 2
Revisions (0)
No revisions yet.