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.
