131 views
3 3 votes

Suppose $g(n) \in \Theta(n^3)$.

Which of the following statements are always true?

  • $\text{S1}:$ $g(n) \in O(n^3)$
     
  • $\text{S2}:$ $g(n) \in \Theta(n)$
     
  • $\text{S3}:$ $g(n) \in \Omega(n)$
     
  1. $\text{S1}$ only
     
  2. $\text{S1}$ and $\text{S3}$ only
     
  3. $\text{S2}$ and $\text{S3}$ only
     
  4. $\text{S1}$, $\text{S2}$ and $\text{S3}$

1 Answer

0 0 votes

Given:

$g(n) \in \Theta(n^3)$

This means $g(n)$ grows exactly like $n^3$ up to constant factors.

Now check each statement.

$\text{S1}$: $g(n) \in O(n^3)$

This is true.

If $g(n) \in \Theta(n^3)$, then it automatically means:

$g(n) \in O(n^3)$

So, $\text{S1}$ is true.
 

$\text{S2}$: $g(n) \in \Theta(n)$

This is false.

$g(n)$ grows like $n^3$, not like $n$.

So, $\text{S2}$ is false.


$\text{S3}$: $g(n) \in \Omega(n)$

This is true.

Since $n^3$ grows faster than $n$, any function growing like $n^3$ is also lower bounded by $n$.

So, $g(n) \in \Omega(n)$


Therefore, true statements are: $\text{S1}$ and $\text{S3}$

Answer : B

Answer:
Position:
Show:

Related questions

4 4 votes
1 1 answer
135
135 views
GO Classes asked Jul 29
135 views
Suppose we have three functions $f(n)$, $g(n)$, and $h(n)$ such that:$f(n) \in O(g(n))\qquad$ and $\qquad g(n) \in O(h(n))$Which of the following statements are guarantee...
4 4 votes
1 1 answer
155
155 views
GO Classes asked Jul 29
155 views
Arrange the following functions in increasing order of asymptotic growth:$f_1(n) = \log(n^n)$$f_2(n) = (\log n)^n$$f_3(n) = \log(n^{6006})$$f_4(n) = (\log n)^{6006}$$f_5(...
4 4 votes
1 1 answer
146
146 views
GO Classes asked Jul 29
146 views
Arrange the following functions in increasing order of asymptotic growth:$f_1(n) = n^{0.999999}\log n$ $f_2(n) = 10000000n$ $f_3(n) = 1.000001^n$ $f_4(n) = n^2$ $f_1(n)< ...
0 0 votes
1 1 answer
172
172 views
GO Classes asked Aug 25
172 views
Let $T_A(n)$ and $T_B(n)$ denote the worst-case running times of two algorithms $A$ and $B$ that solve the same problem.We say that $A$ is asymptotically more efficient t...