The Gateway to Computer Science Excellence
+1 vote
90 views

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.

in Algorithms by | 90 views
+1

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 n2

$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.

2 Answers

0 votes

In d above equation which is given 1/2 n2-3n=Theta(n2) d leading coefficient is 1/2 coz nis of highest degree here. So certainly d answer will depend on more of d leading term. Yeah and 1/2 being d coefficient of n2. In essence nis 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. 

by Boss (13.7k points)
0 votes

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

c1n2  ≤ 1/2n2−3n ≤ c2n2    

And values given to c1 and c2 is one of the case which proves the condition .

by Junior (549 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,159 answers
193,768 comments
93,764 users