complexity

Question

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

Answer 1

Regarding first statement : 

(n + a)^b   =  n^b  +   ^bC₁ n^b-1 . a  +   ^bC₂ n^b-2 . a²  + ....................

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

              =  Ώ(n^b)  and O(n^b) and θ(n^b) 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  n^a+1   =   θ(n^b)   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   n^a+1   =  Ώ(n^b) is correct asymptotic notation for given LHS - RHS pair.Hence second statement is false.

Comments

theta(n^b+1) would have been right? for the second statement?

@habib sir please answer to this one too

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

---

Yes in that case it would be true .

Acyclic graph directory structure should be more flexible than tree directory structure because in the first one , updation of file is easier in case two users in two different user directories but having same file . So in tree directory structure we need to update in both of the user level directories whereas it is not needed to do twice in case of acyclic graph directory structure .

---

@habib sir can u also jus explain in simple words how acyclic graph directory is stored and how a simple tree is?