Thread: Big OH Notation help

Problem 1. Find a function g such that $\displaystyle N^2$ = Θ (g(n)).
Problem 2. Find a function g such that $\displaystyle 2N^2 $= Θ (g(n)).



I need help with these two problems.
Ive never seen the theta sign before.

from what I understand theta means that, T(N) = Θ(h(N)) if and only if T(N) = O(h(N)) and T(N) = Ω(h(N))‏.


for the first would $\displaystyle 2n^2$ work?

If $\displaystyle f(n)=\Theta(g(n))$ then $\displaystyle c_1g(n) \leq f(n) \leq c_2g(n)$ for some positive real constants $\displaystyle c_1$ and $\displaystyle c_2$.

In other words, what we're looking for is the order of $\displaystyle f(n)$.

What is the order of $\displaystyle C\cdot n^2$ where $\displaystyle C$ is some constant?

Originally Posted by Spec

If $\displaystyle f(n)=\Theta(g(n))$ then $\displaystyle c_1g(n) \leq f(n) \leq c_2g(n)$ for some positive real constants $\displaystyle c_1$ and $\displaystyle c_2$.

In other words, what we're looking for is the order of $\displaystyle f(n)$.

What is the order of $\displaystyle C\cdot n^2$ where $\displaystyle C$ is some constant?

would it be just n^2 for both?