Ofcourse there exist constants C1 and C2.. ..

Dark Mode

Chaitanya Kale
asked
in Algorithms
Nov 10, 2022

148 views
0 votes

0 votes

NOTE : $2^{n+1} = 2(2^{n})$ and $2^{2n} = (2^{n})^{2}$

thus, f($2(2^{n})$) = Θ$(2^{n})$ but f($(2^{n})^{2}$) $\neq$ Θ$(2^{n})$

$f(2^{2n})\neq Θ(2^{n})$

=> $f(2^{2n})=> 2^{n}.2^{n}$ i.e. $f(2^{an})\neq Θ(2^{n})$ only if a>1\

same way $f(2^{n/a})\neq Θ(2^{n})$

=> if a= 2 then

$f(2^{n/a}) = > (2^{n})^{1/2} = > \sqrt[2]{(2^{n})}$

as “**a**” increases, the value decreases

it should be represented as

$f(2^{n/a}) = BigO (2^{n})$ i.e. upper bound