Question

10 points 4. One can obtain an asymptotically tight bound directly by computing a limit as n goes to infinity. Essentially, if the ratio of functions f(n) and g(n) converges to a positive constant as n goes to infinity, then f(n) e (g(n)). Let fand g be two functions that Lim f(n)/g(n) n0 exists and is equal to some number c > 0. Then f(n) 0 (g(n)) Prove the above statement

Answer 1

posithe and fn)-n) as to prove this the Jimit exists and fs We Can Shoo that fo)= O(gn). requined dafinition et 'o. Since, C 0 taleasfom detinitien of there is some n beo a limit that This the ohich the 3atio is betwen c and ahvays 2C Thus all nno fe, fin= 0gin) and fin) c g for all nno C. ie, fin)= gm) From & , f gin) CS Scanned with CamScanner