i'm learning algorithm analysis, about the different notations, and in class we wrote an example:
f(n) = 1/2*n^2 + 3n,
and wrote it using O-notation, Ω-notation and Θ-notation:
T(n) = Ω(n)
T(n) = O(n^2)
T(n) = Θ(n^2)
now i'm reading the book, where it says f(n) = Θ(g(n)) is true if and only if both f(n) = O(g(n)) and f(n) = Ω(g(n)) are correct.
in the example we wrote, it says T(n) = Θ(n^2) (which i do agree with) which means both T(n) = O(n^2) and T(n) = Ω(n^2) should hold. but we wrote T(n) = Ω(n). i think that's incorrect? (we wrote that because of the term 3n which means that at least 3n operations are done)
i think it should be T(n) = Ω(n^2) instead of Ω(n)
please correct me if i'm wrong. thanks in advance
f(n) = 1/2*n^2 + 3n,
and wrote it using O-notation, Ω-notation and Θ-notation:
T(n) = Ω(n)
T(n) = O(n^2)
T(n) = Θ(n^2)
now i'm reading the book, where it says f(n) = Θ(g(n)) is true if and only if both f(n) = O(g(n)) and f(n) = Ω(g(n)) are correct.
in the example we wrote, it says T(n) = Θ(n^2) (which i do agree with) which means both T(n) = O(n^2) and T(n) = Ω(n^2) should hold. but we wrote T(n) = Ω(n). i think that's incorrect? (we wrote that because of the term 3n which means that at least 3n operations are done)
i think it should be T(n) = Ω(n^2) instead of Ω(n)
please correct me if i'm wrong. thanks in advance