0
$\begingroup$

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.

  1. $T(n) = T(n-2)+n$
  2. $T(n) = 2T(\sqrt n)+1$
  3. $T(n)=T(n-1)+1/n$
  4. $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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you solve this question as an example? How do we find $A$? Where does the equation $T_p = An$ come from? How do we find the characteristic equation? What equations are we combining? What happens if the equation is homogeneous? $\endgroup$ – Bob Jonas Oct 22 '14 at 4:46
  • $\begingroup$ en.wikipedia.org/wiki/Recurrence_relation#Solving $\endgroup$ – Alan Wang Oct 22 '14 at 4:56
  • $\begingroup$ These aren't methods I'm expected to know. These questions were on a 1-hour exam, so I'm assuming there's a relatively quick method to discover what the asymptotic bound is (or a close approximation to it). $\endgroup$ – Bob Jonas Oct 22 '14 at 4:59
  • $\begingroup$ It's a good idea to find $T_h$ first. That's how you know to use $T_p=n(An+B)$ instead of $T_p=An+B$. $\endgroup$ – bof Oct 22 '14 at 4:59
  • $\begingroup$ @bof ok, edited. $\endgroup$ – Bob Jonas Oct 22 '14 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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