Paragraph from Coreman. Can anyone explain me this in simplified manner.

Question

HI i am trying to understand what author is trying to explain in the below para. However i understood the meaning of Theta(n^2) but if anyone can explain me this para in simplified way it will be

great help.

Comments

Try to explain what is $\Theta$ Notation.

$\frac{1}{2}x^{2} - 3n = \Theta(n^{2})$

What $\Theta$ Notation says LHS and RHS are almost equal Not neccesorily exact equal ( by some constant).

$c_{1}x^{2} \leq \frac{1}{2}x^{2} - 3n \leq c_{2}n^{2}$

Next he cancle n²

$c_{1} \leq \frac{1}{2} - \frac{3}{n} \leq c_{2}$

Now we can take some values of n then Both LHS and RHS are same.

Answer 1

In d above equation which is given 1/2 n²-3n=Theta(n²) d leading coefficient is 1/2 coz n² is of highest degree here. So certainly d answer will depend on more of d leading term. Yeah and 1/2 being d coefficient of n². In essence n² is of highest order and n only has order 1.Now d ques comes of determining d values of constants c1 and c2 respectively.

For d right hand side equality part as regards value of c2 is concerned it is 1/2 coz it is d coefficient of d highest degree. Therefore value  of c2 is 1/2 and n is greater than or equal to 1. This covers d right hand side equality part. 

However I m not able to understand how c1 has come as 1/14 for d left hand side inequality part. This then too solves 3/4th of ur explanation. 

Answer 2

In simple language it means that there are some constant present which can satisfy following condition.

c₁n²  ≤ 1/2n²−3n ≤ c₂n²    

And values given to c_¹ and c₂ is one of the case which proves the condition .