Recurrence Relations

Recurrence	Algorithm	Big-Oh Solution
T(n) = T(n/2) + O(1)	Binary Search	O(log n)
T(n) = T(n-1) + O(1)	Sequential Search	O(n)
T(n) = 2 T(n/2) + O(1)	tree traversal	O(n)
T(n) = T(n-1) + O(n)	Selection Sort (other n2 sorts)	O(n2)
T(n) = 2 T(n/2) + O(n)	Mergesort (average case Quicksort)	O(n log n)

Recurrence of form
1.T(n)= T(k) + T(n-k+1)+C
2.T(n) =T(k)+T(n-k+1)+O(n)
3.T(n)=2T(n/2) +O(n)

solution
1. O(n) , relation T(..) on right contributing also Th(n)

2. O(nlogn) ,O(n) contributing to the time complexity

3.same as 2,O(n) contributing to the time complexity

solver recurrence
1) T_n=3T_n/2       
   Tn = 3(3T_n/2²) = (3ⁱ )Tn/2ⁱ =
   3^log₂n =n^log₂3
2) Tn = 3Tn−1+2.
   3ⁿ − 1.
3) Tn = 2T(n−1) + 2.
   2ⁿ⁺¹ − 2.

Lame’s theorem (Complexity of the Euclidean algorithm). Let a and b be positive integers with a ? b, n be the number of divisions used by the Euclidean algorithm to find gcd(a, b) and k is the number of decimal digits in b. Then n <= 5k.Note that k <= log10 b?+1. Therefore, n = O(log b) divisions are used by the Euclidean algorithm.

Couting problems with Recurrence Relations

Problem Find number of bit string s with no two consecutive 0's
lets call an be number of  bit strings of lenght n where we do not  have 2 consecutive zeros
1) number of bitstrings ending with 0 that should have 1 with them, that is of the form
----|10 and the first part can be occupied by any valid bit string that itsself donot have consecutive zero that is an-2
2) number bit strings ending in 1, ----|1 which is an-1
so an = an-1 + an-2 where initial conditions should be specified for a0 a1 and a2
a0 = 0
a1=2 {0,1}
a2 = 3{01,10,11}
the recurrence seems to be like Fibonacci sequence where a1 corresponds to f3, a2 to f4  i.e  an = Fn+2
This is also relation for subsets of n numbers which do not contain consecutive number
{1,2,3} subsets are F(5) i.e {empty,{1},{2},{3},{1,3}} 5 subsets

Problem Count all number of n digit where number of zero is even
1)any number of for 9,57 which has no zero is valid, and such numbers in form of recurrence is
n-1|9 , n-1|8 , n-1|7... that is all strings ending in some non zero digit and having first n-1 as valid string
i.e 9*an-1
2)we have not counted any number which has zero digit in it ...(we use little to much recursive thinking here)
numbers with zero digit can be formed by adding a zero to number with even number of zeros
number with even number of zeros = total numbers - number with odd zeros(which we have named an)
 10^n-1 - an-1
we get final reccurence as an = 8an-1 + 10^n-1

Solving Recurrence Relations


www.cs.duke.edu/courses/cps130/.../Homeworks/Solutions/H2-solution.pdf   //order of growth problem
www.cse.psu.edu/~berman/sol_565_1.pdf

1) If f(n) = Th(g(n))  { 0<=c1g(n) <= f(n) <= c2g(n) } for some n>= n0 and c1,c2,n0 >=0 
then f(n) = O(g(n)) because it implies 0<= f(n) <= c2g(n)

2)For polynomials p(n) = Th(n^d)

3)o notation
if f(n) = o(g(n))
f(n) becomes insignificant relative to  g(n) for large values of n


4) if
f(n) = w(g(n))



Comparing various functions time complexity
5) exponential and polynomial function
exponential functions with base greater than 1 grows faster than polynomial functions that is
n^b = o(a^n) for a > 1
lim{n->infty} ( n^b / a^n)  = 0

6)exponential e^x
e = 2.71828e^x = {sum o to inty}  x^i / i!
i.e e^x  >= 1+ x
when x = 0 its equality
if |x| <=1
e^x <= 1+x+x^2
so e^x = 1+x+Th(x^2)

7)logarithm functions
polylogatithmic functions grow more slowly than polynomial in the similar manner like polynomial grows slowly than exponential
we use substitution to prove that
substitute log n for n and 2^a for a


a^(log_bc) = c^(log_ba)
 abc converts to reverse, cba


8)
Transitivity is true for all five operators like
f(n) = O(g(n)) and g(n) = O(h(n)) then
f(n) =O(h(n))

Reflexivity is also true for O,Th and Omega that is for all asymptotic tight bounds
f(n) = O((n))

Symmetry is true for Th only that is
f(n) = Th(g(n)) if and only if  gn = Th(f(n))

Case when we might not be able to compare function like in case of
trignometric functions which oscillates n^(1+sin n) and n here 1+sin n oscillates between 0 and 2