A small correction. You need to prove if f(n) = O(g(n)). My Proff (under Note) is for f(n) = Ω(g(n))
On Sat, Jul 31, 2010 at 12:08 AM, sourav <souravs...@gmail.com> wrote: > f(n) = sqrt(n) [squate root of n] > g(n) = log(^2) [log of (n square)] > > For the above pair of functions is f(n) = Ω(g(n))? i.e., is there some > c > 0, such that f(n) >= g(n) for all n? Give proof in case answer is > yes or no. > > --------------------------------------------------------------------------------------------------------------------------------------------------- > Note: f(n) = O(g(n)) is proved as below. Need to find if f(n) = Ω(g(n) > also. > Let a = √(n), then log a = 1/2(log n) > As logarithm of a number is smaller than the number, we have > a > log a > => √n > 1/2(log n) > => √n > 2/4(log n) > => √n > 1/2(log n^2) > Hence √n is > log (n^2) for c = 1/4 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
