Recurrence relation time complexity questions

Q1Quick sort recurrence relation is 
                   T(n)=T(n-1)+n
find worst case time complexity .

 

T(n)=T(n-1)+n
Find T(n-1)
T(n-1)=T(n-1-1)+n-1
T(n-1)=T(n-2)+n-1
Put the value of T(n-1) in T(n)
T(n)=T(n-2)+n-1+n
T(n)=T(n-2)+2n-1
...
In general
T(n)=T(n-k)+nk-1
Let n-k=0
        k=n
Put the value of k
T(n)=T(n-n)+n*n-1
T(n)=T(0)+n^2-1
T(n)=1+n^2-1
T(n)=n^2
So time complexity of quick sort=O(n^2)

Q2.Linear search  recurrence relation is 
                   T(n)=T(n-1)+1
find worst case time complexity . 

T(n)=T(n-1)+1
Find T(n-1)
T(n-1)=T(n-1-1)+1
T(n-1)=T(n-2)+1
Put the value of T(n-1) in T(n)
T(n)=T(n-2)+1+1
T(n)=T(n-2)+2
...
In general
T(n)=T(n-k)+k
Let n-k=0
        k=n
Put the value of k
T(n)=T(n-n)+n
T(n)=T(0)+n
T(n)=1+n
T(n)=n
So time complexity of linear search=O(n)

Q3.Fibonnaci series  recurrence relation is 
                   T(n)=T(n-1)+T(n-2)+c
find worst case time complexity . 

T(n)=T(n-1)+T(n-2)+c
Let T(n-1)==T(n-2)
T(n)=2T(n-1)+c
Find T(n-1)
T(n-1)=2T(n-1-1)+c
T(n-1)=2T(n-2)+c
Put the value of T(n-1) in T(n)=2(2T(n-2)+c)+c
T(n)=4T(n-2)+2c+c
T(n)=2^2*T(n-2)+3c
...
In general
T(n)=2^k*T(n-k)+(k+1)c
Let n-k=0
So k=n
Put the value of k
T(n)=2^nT(0)+(n+1)c
So worst case time complexity of Fibonacci series=O(2^n)

Q4.Tower of hanoi  recurrence relation is 
                   T(n)=2T(n-1)+1
find worst case time complexity . 

T(n)=2T(n-1)+1
Find T(n-1)
T(n-1)=2T(n-1-1)+1
T(n-1)=2T(n-2)+1
Put the value of T(n-1) in T(n)=2(2T(n-2)+1)+1
T(n)=4T(n-2)+2+1
T(n)=2^2*T(n-2)+3
...
In general
T(n)=2^k*T(n-k)+(k+1)
Let n-k=0
So k=n
Put the value of k
T(n)=2^nT(0)+(n+1)
So worst case time complexity of tower of Hanoi is series=O(2^n)

  

Q5 Factorial recurrence relation is 
                   T(n)=T(n-1)+c
find worst case time complexity .  

T(n)=T(n-1)+c

T(n-1)=T(n-1-1)+c

Put the value of T(n-1)

T(n)=T(n-2)+2c

In general term

T(n)=T(n-k)+kc

n-k=0

n=k

T(n)=T(0)+kc

T(n)=1+nc

T(n)=O(n)