I am starting to learn recurrence relations in class and I am having issue with this example:

T(N) = 2N - 1 + T(N-1)

I am bit confused as to get the base case. I'm sorry if this seems elementary, but I am having a difficult time grasping this concept.

Thank you for your help!

  • $\begingroup$ A recurrence relation always has a recurrence (in this case $T(N) = 2N - 1 + T(N-1)$) and a base case (which might be for example $T(0) = 0$, $T(0) = 1$, or $T(0) = 2$). You have written here only the recurrence. So there is no base case. Are you trying to find the base case? It could be anything from what you wrote down. What is $T$ here? $\endgroup$ – 6005 Feb 26 at 19:02
  • 1
    $\begingroup$ @6005 Is right. In general, you cannot infer the base case from the recurrence relation. Without knowing what the problem you were modeling was you haven't a clue. (Base $T(0)=0$ gives a nice solution.) Welcome to the site! $\endgroup$ – Rick Decker Feb 26 at 19:53

In applications to time complexity of algorithms, you are often only interested bounding the growth (i.e., $O(), \Omega()$ asymptotics), and often the initial values incide as multiplicative factors to the solution (or their influence is swamped by the growth of terms that don't include them). So you'll often see sloppy statements that omit initial values.

| cite | improve this answer | |

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.