For which case f(n) != O(g(n)) and g(n) != O(f(n)) is true?
I have following answer to this which i could not understand:
Sometimes true: For f(n) = 1 and g(n) = ||n ∗ sin(n)|| it is true, while
for any f(n) = O(g(n)), e.g. f(n) = g(n) = 1, it is not true.
Please someone help in understanding :
f(n) != O(g(n)) is true if for any given k and any given N there is a n >= N such that f(n) > k*g(n).
An example of both f(n) != O(g(n)) and g(n) != O(f(n)) being true at the same time would be the following: Lets define f(n) = 0 for even n and f(n) = n for odd n. Similarly lets define g(n) = n for even n and g(n) = 0 for odd n. Now obviously f(n) > kg(n) for all odd n no matter how big we choose k and similarly g(n) > kf(n) for all even n no matter how big k is.
Your example of f(n) = 1 and g(n) = ||n ∗ sin(n)|| would also work, since g(n) is oscillating and getting the value 0 for arbitrarily big n, but also getting arbitrarily great values which is enough for our definition of f(n) != O(g(n)) and g(n) != O(f(n)) since f remains the constant function 1
f(n) != O(g(n))then it must follow thatf(n) = ω(n), and this immediately contradictsg(n) != O(f(n)).||in your example is probably the absolute value.