what is the tightest bound for the below functions ?

Question

n² + O(n²⁾  = Theta(n²)  

I am not getting how can we say that tightest bound is in terms of theta , because theta(n² ) implicitly implies Big-Omega(n² ) and Big O(n² ) , Now If we say the function f(n) is Big-Omega(n² ) , then f(n) can be any of the functions >= constant*n²  

but on LHS , we will never get a function greater than n²  so how can we say the tightest bound to be Big-Omega(n² ) ?

 

Please explain  briefly .

Comments

Please read cormen..

---

$n^2$ + O($n^2$) = $\Theta$($n^2$)

$n^2$ + a$n^2$+bn+c = $\Theta$($n^2$)

(a+1)$n^2$+bn+c = $\Theta$($n^2$)

(k)$n^2$+bn+c = $\Theta$($n^2$)

O($n^2$) = $\Theta$($n^2$)              as  c1g(n) ≤ f(n) ≤ c2g(n)      or  f(n) = c2g(n) it is condition of  $\Theta$

Hence Proved

 

Answer 1

The definition of theta says it all

$c_1 g(n) \leq f(n) \leq c_2 g(n)$

if f(n)=$\theta(g(n))$ for some constants $c_1$ and $c_2$ and for all n$\geq n_o$

Your g(n) must be a function such that by means of some constants c1 and c2, you are able to satisfy both the lower bounds and Upper bounds (i.e.

$c_1g(n)$ for big omega and $c_2g(n)$ for big Oh.)

and if you are able to do so with the help of a function called g(n), then your function f(n) is in $\theta(g(n))$ means in simple language you have f(n)=g(n).

So in your example $n^2 + O(n^2)$ the $O(n^2)$ means this term has upper bound of $n^2$ and this term may be a constant, or a linear function of n or a quadratic function of n but not more than this.

Since the term $n^2$ is already there along with big oh, it must be at least $n^2$ in terms of growth of function and it cannot exceed $n^2$ in terms of growth of this function.