Asymptotic Notation

Question

Given that, f(n) = O(g(n)) then it implies that h(f(n)) = O(h(g(n)).
State TRUE/FALSE with proper Explanation/Examples.Please provide mathematical proof,don't just prove by giving a counter example

Comments

what u mean by mathematical proof,don't just prove by giving a counter example

---

i mean please mathematically express the question (i mean f(n)<=cg(n))and then put the given question in it and then give the example....i think it would be hard to find the counter example in the exam..

Answer 1

$f(n) = O(g(n))$

means there exists an $N$ and $C$ such that

$f(n) \leq C.g(n), \forall n > N$.

Now, we apply a function $h$ on either side. Will the equation holds true?

• Case 1: Consider $f(n) = C. g(n), \forall n > N, C > 1$. Now, it is clear that value of $f(n) > g(n)$ for all large $n$ (though their growth rates are the same). So, if we take $h$ as any exponential function $h(f(n)) > h(g(n))$ or $h(g(n)) = o(h(f(n))$ (small o). The given statement is false. 
• Case 2: We alreayd proved that the statement is false. Now, suppose the statement given says small-o $(<)$ and not big-O $(\leq)$. In this case the statement holds true provided $h$ is a strictly (monotonically) increasing function - i.e., as the input increases value of $h$ also increases. If we consider a decreasing function like $\frac{1}{x}$, then the statement is false.

Comments

if  f(n)>g(n) their graowth rates are the same as u told

then f(n) = O(g(n)) is also false

then why do we prove h(f(n)) = O(h(g(n))

---

If $f(n) > g(n)$, for all $n$, then $f(n) = O(g(n))$ is false

This is not true. Consider $f(n) = 2n$ and $g(n) = 3n$.Here, $f(n) = O(g(n))$. 

When we say order of we are talking about growth rate, not actual values. i.e., why we ignore constant factor. But when we want to get actual value constants are important. Also, if the growth rate of a function is higher compared to other, its actual value will eventually grow higher and this is the mathematical statement of $f(n) \leq Cg(n), \forall n > N$, where $N$ represent the particular input point at which the higher growing function takes over the other.

---

@Arjun. For case 1, if C<1, then g(n) > f(n), right?

---

Yes, that's a mistake. Corrected. Thanks.

Answer 2

It is TRUE

Say,

g(n)=n²

f(n)=log n

Now put n=2^x

So, g(n)=2^2x

f(n)=x

So, f(n)=O(g(n))

Now, h(n)=n³

g(n)=(n²)³

f(n)=(log n)³=n⁶

Now, putting n=2^x , we get

h(g(n))=2^6x

h(f(n))=x³

Hence proved h(f(n)) = O(h(g(n)).

Comments

@Tauhin

Acc to Anirudh link

if it is not constant we cannot conclude big O

---

the link doesn't say we cannot conclude....

it says...by looking the ratio...we can tell it doesn't hold means...it is false..

---

@anirudh , by your example, It is showing false, but by srestha's example , it is showing true... please clear me the concept...

Answer 3

f = $x$

g= $x^2$

So, f = $O(g)$

Now, let 'h' be inverse function.

So, $h(f)$ ≠ $O(h(g))$