T(n) = T(n-2) + 1 for all n > 2. where T(1) = T(2) = 1. Find the even case and odd case.
Recursion relation
Given that T(n) = T(n - 2) + 1
T(n) = (T(n - 4) + 1) + 1 (By putting T(n - 2) = T(n - 4) + 1 while assuming n-2 > 2)
T(n) = T(n - 4) + 2
Now put value of T(n - 4) = T(n - 6) + 1 in above equation assuming that n - 4 > 2
T(n) = T(n - 6) + 3
From this, we make a hypothesis that T(n) = T(n - 2*k) + k (where k is any integer)
To prove the above hypothesis, we apply mathematical induction on k
Base case : k = 1
Then above becomes T(n) = T(n - 2) + 1 (This is true by given recurrence in question)
Hypothesis step : we assume that T(n) = T(n - 2*k) + k is true for k.
Inductive step : We will prove it for k + 1 given that it is true for k
To prove : T(n) = T(n - 2*(k + 1)) + (k+1)
T(n) = T(n - 2*k - 2) + (k + 1)
T(n) = T((n - 2*k) - 2) + (k + 1) [Equation 1]
Now T(n - 2*k) = T((n - 2*k) - 2) + 1 [From recurrence relation given in question]
So putting this value in Equation 1, we get
T(n) = T(n - 2*k) + k
and we know that above equation is true from hypothesis step,
So our hypothesis is true that T(n) = T(n - 2*k) + k from some integer k
Now,
Odd case : n is odd
we know that n is odd and 2*k must be even (for any integer k), So n - 2*k is odd.
so we will find value of k for which n - 2*k = 1
k = (n - 1)/2 (Note that n is odd so n - 1 is even there (n - 1)/2 must be integer)
now put value of k = (n - 1)/2 in equation T(n) = T(n - 2*k) + k
T(n) = T(n - 2*(n - 1)/2) + (n - 1)/2
T(n) = T(n - (n - 1)) + (n - 1)/2
T(n) = T(1) + (n - 1)/2
T(n) = 1 + (n - 1)/2 (Given T(1) = 1)
T(n) = (n + 1)/2 where n is odd
Even Case : n is even
We know
T(n) = T(n - 2*k) + k from some integer k
n is even and 2*k must also be even (for any integer k), So n - 2*k must also be even
We will find value of k for which n - 2*k = 2
k = (n - 2)/2
put value of k in equation T(n) = T(n - 2*k) + k
T(n) = T(n - 2*(n - 2)/2) + (n - 2)/2
T(n) = T(n - (n - 2)) + (n - 2)/2
T(n) = T(2) + (n - 2)/2
T(n) = 1 + (n - 2)/2 (T(2) = 1)
T(n) = n/2 where n is even
--------------------------------------------------------------------------------------------------
PS : If you have any doubt regarding this solution please comment and if you like this solution then please upvote.
Thanks
please derive the binary recurrence equation ie t(n) = t(n/2) + 1, t(1)=1 given that n is not restricted to be power of two by considering the case that n can either be an odd or even number.
Solve the recurrence relation T(n) = 2T(n / 2) + 3n where T(1) = 1 and k n = 2 for a nonnegative integer k. Your answer should be a precise function of n in closed form. An asymptotic answer is not acceptable. Justify your solution.
Solve the recurrence relation using a recursion tree AND substitution method: T(n) = T(n-1) + 10n
2gcd(a/2, b/2) if a, b are both even ged(a, b/2)if a is odd, b is even ged(a,bged(a/2, b) if a is even, b is odd gcd(a -b)/2, b) if a, b are both odd (b) Give an efficient divide-and-conquer algorithm for greatest common divisor, based on the above. (c) Express the running time of your algorithm for the case where a and b are both n-bit numbers. Recall that dividing by two results in the removal of one bit from...
y = x" + x"-2 + ... + 1, where n + 1. where n = odd and f(5) = 137. Find the value of f(-5). Done
Solve the recurrence relation using a recursion tree AND substitution method: T(n) = 2T(n - 1) + 10n.
How to get the big-O for the following recursion relation:T(1)=1, T(2)=1.5, T(N)=1.5T(N/2)-0.5T(N/4)-1/N.
2. The Chebyshev polynomials can be determined from T.(x) = cos(n cos-?x). (a) Find T-(x) from above formula. (b) Find Tn+1(x) + Tn-1(x) in terms of T,(x). (c) Show that In/2] n! Tn () = KO (2k)! (n – 2k);?"*2*(x2 – 1)". (Note: You need to prove it in detail. To do it, you may need to consider two cases: n=2p-1 (odd) and n=2p (even). )
4. Define a function f:N → Z by tof n/2 if n is even 1-(n + 1)/2 if n is odd. f(n) = Show that f is a bijection. 11 ] 7. Let X = R XR and let R be a relation on X defined as follows ((x,y),(w,z)) ER 4 IC ER\ {0} (w = cx and z = cy.) Is R reflexive? Symmetric? Transitive? An equivalence relation? Explain each of your answers. Describe the equivalence classes [(0,0)]R and...
2, For the following periodic series, f(t) = t^2, ( -1<t<1), period = 2 (a) graph this periodic function, range is ( -8<t<8), and find a key point (b)Even function or odd function? (c ) find a Fourier series