TS

Question

$\text{Please explain True or False and Why ?}$

$\text{1. f(n) = O(f(n/2))}$

$\text{2. f(n) = O($f(n)^{2}$) }$

Answer 1

1. False. here f(n)>f(n/2) as a function, we know that smaller functions are in order of bigger functions,

for f(n)=O(g(n/2)) here the constant associated with the 2nd function is 1/2 ie to be an order f(n)<c*f(n) such that the value of c>1; so for values lesser than 1(1/2 in this case) it means bigger function is in order of smaller function which is not possible. THUS FALSE

2.False.

in case the function is n^0.5 the value of f(n)=n^0.5 whereas f(n)^2=n^0.25 which is lesser , thus bigger function is in order of smaller function which is not possible thus FALSE