Question

Which of the following is not O(n^2)?
O
(15410) * n + 12099
O
n^1.98
O
n^3/ (sqrt(n))
O
(2^20) * n​

Answer 1

This is the answer to this question

Answer 2

Complete question

"Which of the following is not O(n^2)?

(A) $(15^{10}) * n$ + 12099

(B)$n^{1.98}$

(C)$n^3 / \sqrt{n}$

(D) $(2^{20}) * n$"

Answer:

(C)$n^3 / \sqrt{n}$

Explanation:

Best answer

The Big-O notation is used to indicate the maximum execution time. This means that the algorithm does not take longer than the binding function.

• $(15 ^ {10}) * n + 12099$ , This polynomial can safely ignore the constant part 12099. This leaves$(15 ^ {10}) * n$. Again, $(15 ^{ 10})$ is a constant and can be ignored. This gives theta (n) restrictions. This theta (n) is always bound by $O (n ^ 2)$.

• $n ^ {1.98}$ is also always bound by $O (n ^ 2).$
• $n ^ 3 / \sqrt{n}$ $= n ^ 3 / n ^ {0.5} = n ^ {2.5}$, you can clearly see that $n ^ {2.5}$ cannot be bound with $n ^ 2$. This increases much faster than $n ^ 2$. Therefore, this cannot be $O (n ^ 2)$.

• $(2 ^ {20}) * n$, like the first case, this is also linear with respect to the input. Therefore, it is also bound to $O (n ^ 2)$.

#SPJ3