retagged by
316 views
0 votes
0 votes
1.(n + a)b = $\Omega$(nb) for all real numbers a , b >0

2.na+1=theta(nb) iff a=b for all real numbers a , b>0

which is true?

Acyclic graph directory structure is more flexible than simple tree structure - true or false
retagged by

1 Answer

Best answer
2 votes
2 votes

Regarding first statement : 

(n + a)b   =  nb  +   bC1 nb-1 . a  +   bC2 nb-2 . a + ....................

              =  nb  [ In asymptotics , we consider the dominant term only when addition terms are there ]

              =  Ώ(nb)  and O(nb) and θ(nb) as well.

Hence the first statement is true.

Regarding the second statement : 

If   a  =  b  , then  

a + 1 > a  and hence a + 1 > b

Hence  na+1   =   θ(nb)   is false as theta notation means that both LHS and RHS may only differ by constant and not by any variable factor . But here LHS is 'n' times more than RHS which is not acceptable for theta notation.

Instead   na+1   =  Ώ(nb) is correct asymptotic notation for given LHS - RHS pair.Hence second statement is false.

selected by

Related questions

1 votes
1 votes
1 answer
1
Kapil asked Aug 5, 2016
597 views
2n is the order of 3n . Is it True or False ? State with reason.
0 votes
0 votes
1 answer
2
gshivam63 asked May 31, 2016
462 views
It is true or false..(log n)! and (log log n)! are polynomially bounded?What does polynomially bounded means?