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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
