Does f in Ω(n) imply f is in O(n^2)?

Question

As n ⇒ ∞, f = Ω(n) ⇒ f = O(n^2).

How can I show if this Omega and Big-O notation is correct?

Seems completely wrong from https://www.tutorialspoint.com/data_structures_algorithms/asymptotic_analysis.htm https://guide.freecodecamp.org/computer-science/notation/big-omega-notation/ and https://stackoverflow.com/questions/12138212/difference-between-big-theta-and-big-o-notation-in-simple-language — B. Go, Mar 14 '20 at 12:40
Are you sure that this is correct? If I have a linear lower bound, does this always mean that I also have a quadratic upper bound? — lyinch, Mar 14 '20 at 12:40

score 2 · Answer 1 · answered Mar 14 '20 at 14:50

2

It's false, and one counterexample is enough to show that it's false.

A simple counterexample is the function f(n) = n³, which is in Ω(n), but not in O(n²).

answered Mar 14 '20 at 14:50

kaya3

1 Answers1