search
Log In
1 vote
189 views

Which of the following is not true in the function $f(n)=2^{n-4}$?

  1. $f(n)$=Θ($2^{n+3}$)
  2. $f(n)$=Ω($n^{1000}$)
  3. $f(n)$=Ο($2^{n-10}$)
  4. $f(n)$=$None$
in Algorithms
edited by
189 views
0
Sorry, not A.

Is D correct?
0
Yes..Please elaborate

3 Answers

2 votes
 
Best answer

$A. f(n)$= Θ($2^{n+3}$)

$f(n) = 2^{n-4} =\Large \frac{2^n}{2^4}$

let $g(n) = 2^{n+3} = 2^{n}.2^3$

$\large \frac{f(n)}{g(n)} = \frac{1}{2^3.2^4}$

this tells us $f(n)$= Θ($2^{n+3}$) is true

 

$B.$ $f(n)$=Ω($n^{1000}$) 

$f(n)$ is exponential and $n^{1000}$ is polynomial so  $f(n)$=Ω($n^{1000}$)  is true

 

C. $f(n)$=Ο($2^{n-10}$) is also true just like A

So none of them are false 

 


selected by
1 vote

Option d.

0 votes
For the first one, we have to show that $2^{n-4} \leq c \times 2^{n-10}$ for all $n \geq n_0$.

This is true for any $c \geq 2^6$ as we get by solving the inequality.

For the second one, we have to prove that $f(n) \geq c \times g(n)$ for all $n \geq n_0$
$\implies 2^{n-4} \geq c \times n^{1000}$.

This is true for all $n_0$ when $n - 1000 \log n > 4$. You can get this inequality by doing using the limit definition while comparing terms.

For the third, we have to show $c_1 \times 2^{n-3} \leq 2^{n-4} \leq c_2 \times 2^{n+3}$.

You can find $c_1, c_2$ according to this condition.

Hence, all three are true.

Related questions

0 votes
1 answer
1
162 views
Consider the following function $f(x)$ = $x^8$+6$x^7$-9$x^5$-$x^4$+2$x^2$-18. Which of the following is true if x is greater than 56? $f(x)$ = O($x^8$) $f(x)$ = Ω($x^8$) $f(x)$ = θ($x^8$) $f(x)$ = None of the above.
asked Dec 7, 2018 in Algorithms Gupta731 162 views
2 votes
0 answers
3
204 views
Let f (n) = Ο(n), g(n) = Ω(n) and h(n) = θ(n). Then g(n) + f(n).h(n) is ______ A.) Ω(n) B.) θ(n2) C.) Ω(n2) D.) θ(n) How to do these type of questions ?
asked Jan 22, 2018 in Algorithms ashish pal 204 views
...