GO Classes 2023 | IIITH Mock Test 1 | Question: 45

Answer 1

@okntk

f(n) = 1/n and f(n)^2 = 1/n^2

f(n) will grow faster than f(n)^2

Comments

can you write counter example for option A, why it is not correct ?

---

@Mukulvyas consider f(n) = 2n  and g(n) = n

we can prove f(n) = O(g(n))  where 2n <= c n

where c(constant) is 3  and n0>1

But now to our problem 2^f(n) = O(2^g(n))

f(n) = 2n and g(n) =n

so 2^2n <= c 2^n

we can’t prove, it because 2^2n = 2^n *2^n

2^n *2^n <= c * 2^n

2^n <= c

cause c is constant it can’t be greater than variable 2^n

So,This option is incorrect.