CODEWITHSUNDEEP
algorithmrecursionrecurrence
juicymango
juicymango

Reputation: 201

Recurrence relation for T(0) = 1, T(1) = 0, T(n ) = 2* T(n-2)

I am trying to find the recurrence relationship for the above expression.

I deduced that:

T(n) = C*T(n-2)

T(n-2) = 2C*T(n-4)

T(n-4) = 3C * T(n-6)

...

T(n) = k/2C * T(n-k)

I am stuck here. Is this the correct approach? What is simplified recurrence relationship without having T in simplified equation?

Upvotes: 0

Views: 799

Answers (2)

Gilbert
Gilbert

Reputation: 141

I wrote a python program and found the relationship:

def rec(num):
    if num == 0:
        return 1
    elif num == 1:
        return 0
    else:
        return 2 * rec(num - 2)

And after several test, I found this rule:

index 2, 3, 4, 5, 6, 7, 8....

result 2, 0, 4, 0, 8, 0, 16....

So the result might be 2^(n/2) when n = 2k && 0 when n = 2k + 1 (k belongs to Z)

Upvotes: 3

meowgoesthedog
meowgoesthedog

Reputation: 15035

Let's observe the behaviour as we expand this function m times:

T(n) = 2^2 * T(n - 2*2)
     = 2^3 * T(n - 2*3)
     = 2^4 * T(n - 2*4)
     = ...
     = 2^m * T(n - 2m)

When n is:

  • Even: n - 2m eventually equals zero, which means that the maximum value is m = n / 2, and that T(n) = 2^(n/2)
  • Odd: " eventually equals 1, which means that T(n) = 2^(...) * T(1) = 0

If we wanted to write this in a single expression:

T(n) = (1 - n + floor[n/2]) * 2^(n/2)

Upvotes: 1

Related Questions