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.