in Algorithms
148 views
0 votes
0 votes
Can we write f(2$^{n/a}$) = Θ(2$^{n}$) for any integer a >0?
in Algorithms
148 views

2 Comments

Ofcourse there  exist constants C1 and C2.. ..
0
0

what if $f(n)=2^n$ ?

0
0

1 Answer

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

edited by

1 comment

and $f(2^{an}) = BigΩ (2^{n})$  i.e. lower bound
0
0

Related questions