Search code examples
complexity-theory

Is there any function f(n) that f(n) is little-o of n and f(n) is big-omega of n?


I want to find f(n) that is cn(definition of big-omega) <= f(n) < cn(definiton of littl-o). Is there any f(n) satisfying this statement?


Solution

  • I want to find to find f(n) that is cn <= f(n) < cn. Is there any f(n) satisfying this statement?

    It is immediately obvious from the inequality that it cannot possibly be satisfied, since it implies cn < cn, and by the very definition of "less than", this can never be true: there is nothing which is smaller than itself.