1

I'm solving some recurrence relation problems for Big O.

T(n) = T(n-1)

I started with:

T(n)   = T(n-1)
T(n-1) = T(n-2)
..
T(n) = T(n-k)

Now setting k to n-1

T(n) = T(1)

So the result is

T(n) = O(1)

I'm not entirely sure if this is correct, but I'm uncertain that this is so easy.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Razer
  • 7,843
  • 16
  • 55
  • 103

1 Answers1

1

As long as you have a base case, yes, that's correct.

I'm assuming the recurrence is defined as

T(0) = k (for some constant k), and

T(n+1) = T(n)

Then you can prove by induction that T(n) = k for all natural numbers n.

  • Base case: If n = 0, then T(n) = T(0) = k, as required.
  • Inductive step: Assume T(n) = k. Then T(n + 1) = T(n) = k, as required.

Therefore, T(n) = k = O(1).

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065