DAA : Recurrence Relation

Updated: Dec 6, 2019

A recurrence is an equation or inequality that describes a function in terms of its values on smaller inputs. To solve a Recurrence Relation means to obtain a function defined on the natural numbers that satisfy the recurrence.



for (i=1; i<=n*n; i++) // Executed n*n times

for (j=0; j<i; j++) //Executed <= n*n times

sum++; //O(1)


Running Time: //O(n4)


But can we get a tighter bound?


Exact # of times sum++ is executed:



Ex. :


void test( int n ) ----------T(n)

{

if( n<5 )

{ printf( "%d", n ); -----------1

test( n-1 ); ------------T( n-1 )

}

}




T( n ) = T( n-1 ) +1 // print and test(n-1) are under test(n)

T( n ) = T( n-1 ) +1 ----[a]


we know : T( n ) = T( n-1 ) +1 so T( n -1 ) = T( n-1-1 ) +1 or T( n-1) = T( n-2 ) +1 ---[b]

and also T( n-2 ) = T( n-3 ) +1 -----[c]


put eq [b] in eq [a]


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


now put eq [c] in eq [a]


T( n ) = T( n-3 ) +3

if we do it again and again

we get some kind of sequence

.

.

.

.

.

T( n ) = T( n-k ) +k //for some constant k

now assume n-k=0 //reach the end

at that end point we can say n=k -----[d]


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

from eq [d]

T( n ) = T( n-n ) +n

T( n ) = T( 0 ) +n

T( n ) = 1 +n //we know T( 0 ) = 1

= Ɵ(n)




  1. Introduction

  2. Asymptotic Notations

  3. Algorithm Design Techniques

  4. Recurrence Relation

  5. Divide and Conquer approach



© 2019 by Techy Bande Official.

Developed By : RK JAMERIA