A N & R R: Symptotic Otations Ecurrence Elations

A SYMPTOTIC N OTATIONS & R ECURRENCE R ELATIONS
F LOW OF THE PRESENTATION
Growth Notations Recurrence Relations Masters Theorem
O -N OTATION
f(n) = O(g(n)) if a positive const. c and nc such that 0 f(n) c.g(n); n nc.
O -N OTATION
Prove n2+2n =O(n2-2n). let n2-2n=g(n) and n2+2n=f(n) g(n)= n2-2n g(n) = n2-2n+(n-n) g(n) =1/2(n2+2n) + 1/2(n2) + (-3n)
g(n) =1/2f(n) + [1/2n2 -3n]

g(n) 1/2f(n) if [1/2n2 -3n+ 0
O -N OTATION
g(n) 1/2f(n) if [1/2n2 -3n+ 0 f(n)2.g(n) if *1/2n2 -3n+ 0 & [1/2n2 -3n+ 0
1/2n -3 0 n 6
that is f(n)2.g(n) n 6
so c=2 and nc=6 such that

f(n) c.g(n); n nc.
f(n)=O(g(n))
O -N OTATION
Is f(n) = O(g(n)) ?

f(n) = n2+n+1 f(n) = n2
g(n) = n2 g(n) = n2+n+1
X X X
f(n) = n2+4n-3
f(n) = n2-3n+6 f(n) = en f(n) = n2lgn f(n) = n2lgn
g(n) = n+2
g(n) = n3+3n-6 g(n) = (an+b)k g(n) = n2 g(n) = n3
-N OTATION
f(n) = (g(n)) if a positive const. c and nc such that 0 c.g(n) f(n); n nc.
-N OTATION
Prove n2+2n = (n2+4n). Prove n2+2n = (n+4) Do it yourself.
-N OTATION
Is f(n) = (g(n)) ?

f(n) = n2+n+1 f(n) = n2
g(n) = n2 g(n) = n2+n+1
f(n) = n2+4n-3
g(n) = n+2
-N OTATION
f(n) = (g(n)) if positive const. c1,c2 and nc such that 0 c1.g(n) f(n) c2.g(n); n nc.
-N OTATION
Is f(n) = (g(n)) ?

f(n) = n2+n+1 f(n) = n2
g(n) = n2 g(n) = n2+n+1
X X X X
f(n) = n2+4n-3
g(n) = n+2
N OTATIONS C ONTD .

f(n) = O(g(n)) g(n) = (f(n)). f(n) = (g(n)) & f(n) = O(g(n)) f(n) = (g(n)). lgk(n) = O(n). nk=O(an). (an+b)k=(nk)
R ECURRENCE R ELATIONS
Describes a function in terms of its values on smaller input.
factorial(0) = 1 factorial(n) = n*factorial(n-1)
fibonacci(1)=0 fibonacci(2)=1 fibonacci(n) = fibonacci(n-1)+fibonacci(n-2)
tower of hanoi problem.

Initial state
Final state
Write the recurrence relation. (Do it yourself)
S OLVING
RECURRENCE
R ELATIONS
T(n) = T(n-1) + (1) T(n) = T(n-1) + c T(n) = [T(n-2) + c] + c T(n) = T(n-2) + 2c T(n) = T(n-3) + 3c T(n) = T(n-k) + k.c
Iterative method
S OLVING
RECURRENCE
T(n) = T(n-k) + k.c Now our base case = T(0) putting (n-k)= 0 k = n putting k = n T(n) = T(0) + c.n T(n) = (1) + c.n T(n) = c1 + c.n T(n) = (n) Running time for factorial = (n)
R ELATIONS
S OLVING
RECURRENCE
R ELATIONS
Substitution Method.
1. 2.
Guess a Solution Use PMI to show that your guess is indeed a solution and find the constants.
Recursion Tree Method.
Total cost = cost of the tree = work done at each level
M ASTER S T HEOREM
Method to solve recurrences of form T(n) = aT(n/b) + f(n). where a1 , b>1 and f(n) = asymptotically +ve fn.
if f(n) = O(nlogba-) for some >0 then T(n) = (nlogba).

if f(n) = (nlogba) then T(n) = (nlogba.lgn).
if f(n) = (nlogba+) for some >0, & if a.f(n/b) c.f(n) for some const. c<1 for large n. then T(n) = (f(n)).
M ASTER S T HEOREM
T(n) = 8 T(n/2) + n2. a=8, b=2, f(n) = n2. nlogba = nlog28 = n3. as nlogba is asymptotically larger than f(n) case I may be applicable. We try to find value of . you can use f(n) = n2 = O(n3-) for = . any 1 Thus from the case I of masters theorem T(n) = (n3)
M ASTER S T HEOREM
T(n) = 4 T(n/4) + n. a=4, b=4, f(n) = n. nlogba = nlog44 = n. case II is applicable. f(n) = n = (n). Thus from the case II of masters theorem T(n) = (nlgn)
M ASTER S T HEOREM
T(n) = 5T(n/5) + n3lgn. a=5, b=5, f(n) = n3lgn. nlogba = nlog55 = n. as nlogba is asymptotically smaller than f(n) case III may be applicable. We try to find value of . you can use 3lgn = (n1+) for = . f(n) = n any 2 Thus from the case III of masters theorem T(n) = (n3lgn)
M ASTER S T HEOREM
T(n) = 4 T(n/2) + n2/lgn a=4, b=2, f(n) = n2/lgn. nlogba = nlog24 = n2. as nlogba is asymptotically larger than f(n) case I may be applicable. We try to find value of . f(n) = n2/lgn = O(n2-) for no >0. Thus masters theorem is not applicable.
P RACTICE Q UESTIONS
Let f(n) and g(n) be asymptotically +ve fns. Prove or disprove
f(n) + o(f(n)) = (f(n))
f(n) = (f(n))
f(n) = O(f(n)2) f(n) + g(n) = ( min{f(n),g(n)} ) f(n) = O(g(n)) g(n) = (f(n))
P RACTICE Q UESTIONS
Solve the following recurrence relations.

T(n) = T(7n/10) + n T(n) = T(n-2) +n T(n) = T(n/2) + T(n/4) + n T(n) = nT(n) + n T(n) = 9T(n/3) + n2/lgn

A N & R R: Symptotic Otations Ecurrence Elations

Uploaded by

Copyright:

Available Formats

A N & R R: Symptotic Otations Ecurrence Elations

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

A N & R R: Symptotic Otations Ecurrence Elations

Uploaded by

Copyright:

Available Formats

A SYMPTOTIC N OTATIONS & R ECURRENCE R ELATIONS

F LOW OF THE PRESENTATION

Growth Notations Recurrence Relations Masters Theorem

g(n) =1/2f(n) + [1/2n2 -3n]

so c=2 and nc=6 such that

f(n) = n2+n+1 f(n) = n2

g(n) = n2 g(n) = n2+n+1

Prove n2+2n = (n2+4n). Prove n2+2n = (n+4) Do it yourself.

f(n) = n2+n+1 f(n) = n2

g(n) = n2 g(n) = n2+n+1

f(n) = n2+n+1 f(n) = n2

g(n) = n2 g(n) = n2+n+1

Describes a function in terms of its values on smaller input.

factorial(0) = 1 factorial(n) = n*factorial(n-1)

fibonacci(1)=0 fibonacci(2)=1 fibonacci(n) = fibonacci(n-1)+fibonacci(n-2)

tower of hanoi problem.

Write the recurrence relation. (Do it yourself)

Recursion Tree Method.

Total cost = cost of the tree = work done at each level

if f(n) = O(nlogba-) for some >0 then T(n) = (nlogba).

Let f(n) and g(n) be asymptotically +ve fns. Prove or disprove

f(n) + o(f(n)) = (f(n))

Solve the following recurrence relations.

You might also like