Search code examples
mathbig-orecurrence

Recurrence Relation: Solving BigO of T(n-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.

Solution

  • 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!