Allen Career Institute: Algorithm

Question

Which of the following is /are TRUE ? S1 : $n^{a} . n^{b} = 0$$((n^{a})^{b})$ for any a, b > 1 S2 : $(n^{a})^{b} = 0$$((n^{a})^{b})$ for any a, b > 1

(1)	Both S1 and S2
(2)	S1 Only
(3)	S2 Only
(4)	Neither S1 nor S2

Comments

both ?

---

answer is S1,

r u sure, it will be both?

---

$n^{a}.n^{b}=n^{a+b}$

is it not?

---

@sresthamam,

can we take a and b as any number between 1 and 2 (1.1,1.6...) and the first one will not be true..

Like a$^{1.6}$.a$^{1.6}$ should be a$^{3.2}$  if we consider n$^{a}$.n$^{b}$=n$^{a+b}$ but first option says it should be a$^{2.56}$ which is not true..

But option 1 will be true for all values >=2 of a and b

---

how you arrive this case @amanverma== ?

---

@Shaik Masthansir,

just took some example values.If both were true, it will be saying like n$^{a}$.n$^{b}$=n$^{a+b}$ and (n$^{a}$)$^{b}$ are equal asymptotically because both are O((n$^{a}$)$^{b}$ ) according to question,but for values less than 2 as mentioned above , (1) fails .

---

OK :)

---

@amanverma==

So, u mean answer should be S2

right?

---

@sresthayes mam

Answer 1

The correct answer is Option (3) S2 Only.

Explanation - 

From wikipedia, big-O notation is defined as, $\ f(x)= O(g(x))$ if and only if there exists a positive real number constant $\ c$ such that $\mid f(x) \mid \le c \cdot g(x)  \space for\space all\space x \ge x_{0} $.

In simpler terms, what it means is, the function inside the big-O, which is an upper bound,  should always be greater than the function to be bounded. 

Consider statement S1 - 

Here

$ f(x) = n^{a}\cdot n^{b} = n^{a + b}$ 

$ g(x) = (n^{a})^{b} = n^{a\cdot b }$

Now from the definition, we need $ f(x) \le c \cdot g(x)$

i.e. we need $(a+b) \le a\cdot b$ 

for the constants $a, b > 1 $.

Now, since it's not explicitly given that a and b are integers, we can take values of a and b as 1.1 and 1.2 

In this case, statement S1 becomes false since, 

$ n^{(1.1+1.2)} \ge n^{1.1 \times 1.2}$ which is why we cannot have the upper bound as given in the statement S1.

 

Now, consider statement S2 - 

This case is simple, since we can write 

$ (n^a)^{ b} \le c \cdot (n^a)^{ b} \space for \space any\space positive\space real\space number\space c $

So, statement S2 is true.