Prove or give a counterexample: for every function f from non-negative integers to non-negative reals, o(f) = O(f) − Θ(f). Here “−” denotes the set minus operation. I try to make some tryout but failed to make the abstract function f to into working, can someone give me some Hints or solutions?

  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Sep 10, 2022 at 19:21

1 Answer 1


Consider $f(n) = n^2$ and $g(n) = \left\{\begin{array}{ll}n & \text{if }n\text{ is even}\\n^2&\text{otherwise}\end{array}\right.$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.