# 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) **