I really need some help solving recurrence relations in a relatively quick manner, so any insight would be highly appreciated. Here are a few of the ones on my midterm sample that I'm struggling with:
You may assume nontrivial base cases, e.g., $T(n)=1$ for $n\le 10$ would be a nontrivial base case. Choose one of (a)-(g) for each.
(a) $\Theta(1)$
(b) $\Theta(\log n)$
(c) $\Theta(n)$
(d) $\Theta(n^2)$
(e) $\Theta(n^2 \log n)$
(f) $\Theta(n\log n)$
(g) other. write the correct answer.
- $T(n) = T(n-2)+n$
- $T(n) = 2T(\sqrt n)+1$
- $T(n)=T(n-1)+1/n$
- $T(n) = T(n/2)+T(\sqrt n)+\sqrt n$
So this is how I typically solve these kind of problems. I know they each produce a tree-like structure, so something like $T(n)=T(n-2)+n$ can be drawn like:
n
|
(n-2)
|
(n-4)
|
...
Which would be $O(n+(n-2)+(n-4)+...) = O(n^2)$
I'm not even sure if this method is right, but it doesn't seem to work obviously for the other problems. Number 3. looks like it has the same form, would the run time also be $O(n^2)$ in this case? I should note that these questions were on a 1-hour exam, so long and meticulous methods, though helpful for general problems, will not help me in preparing for my exam.
From what I have learned, first you need to determine whether the equation is homogeneous or not. For example one, $$T(n)-T(n-2)=n$$ So it is not homogeneous, so you need to let $$T_p=n(An+B)$$ and you need to find the constant $A$. Then you have to change the equation into characteristic equation. $$r^2-1=0$$ Find the characteristic roots to form $T_h$. Combine $T_p$ and $T_h$ will be the solution.