Consider functions f(n) = n^2 and g(n) = (1 + (-1)^n)n^2. What is the asymptotic relationsip (f is big-theta(g), f is big-omega(g) or f is big-O(g)) between the two functions?
I have graphed the g(n). It fluctuates between 0 and 2n^2. It does seem to satisfy c1g(n) ≤ |f(n)| ≤ c2g(n), but it does not quite satisfy for all n > n0. Because only at the points (not an interval), g(n) is greater than or smaller than f(n). Is there no asymptotic relationship between f(n) and g(n) because it cannot satisfy the condition "for all n > n0"?