How to prove the complexity of an algorithm?

Question

I have some questions about analyzing algorithm complexity, I have their correct answer (true or false), but I don’t know how to prove it, if someone can explain me the reasoning to get their real proof:

1. 100n is not in Ω(n²) -> Jig says it is true.
2. n + log n is in Θ(n) -> Feedback says it is true
3. We can say that an algorithm with complexity f(n) is in O(f(n/2)). -> Template says it is false.
4. A function f(n) asymptotically dominates another function g(n) if there are two positive constants c and n_0 such that, for n n_0, we have f(n) c g(n). Jig says false.
5. For two functions g(n) and f(n) we have that f(n)=Ω(g(n)) if only if f(n)=O(g(n)). template says it is false.

Answer 1

In asymptotic analysis, who dominates is the term with greater magnitude. For example, in the expression:

N³ + 1000N² + 10000N + 1000000, who dominates is O N³. This pq according to N goes to infinity, the value of the other terms becomes derisory near N³.

Then, evaluating the propositions.

• 1: 100N is not in O(N²): True. 100N is in O(N), pq the exponent of the greatest term is 1.
• 2: N + logN is in O(N): True. N grows much faster than logN and therefore dominates the expression.
• 5: f(n) = Ω(g(n)) if and only if f(n) = O(g(n)) => Ω(g(n)) = O(g(n)). What this expression is telling us is that for a function to be equal to the best case of another function, it must also be equal to the worst case, which is absurd. Just take a function whatever has better case other than the worst case, which will contradict that proposition by proving its falsehood.

The third seems to me that the feedback is wrong, and the fourth does not know how to answer. I ask you to consult your teacher and return me, also I want to know.

I hope I’ve helped ;)