DAA : Recurrence Relation

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