algorithm - Why is only one of the given statements about complexity classes correct? -


apparently correct answer following question (c), why other options not correct until know value of n?

if n=1, of these seem correct except (b)! going wrong?

which of following not o(n2)?

(a) 1510 * n + 12099
(b) n1.98
(c) n3 / √n
(d) 220 * n

wikipedia says :-

big o notation describes limiting behavior of function when argument tends towards particular value or infinity, in terms of simpler functions. description of function in terms of big o notation provides upper bound on growth rate of function.

an upper bound means f(n) = n can expressed o(n), o(n2), o(n3), , others not in other functions o(1), o(log n).

so, going in same direction, can eliminate options shown below :-

  1. 1510 * n + 12099 < c * n2, n > √12100 i.e. n > 110 --- hence o(n2).

  2. n1.98 < n2, n > 1 --- , o(n2).

  3. n3 / √n = n5/2 > n2 n > 1 --- hence, isn't o(n2).

  4. 220 * n = 1024*1024*n < c* n2 n > 1 ,where c = 1024*1024 --- hence, o(n2).

hence, option doesn't satisfy o(n2) option c,i.e., f(n) = (n^3 / (sqrt(n))). here, so, (n3 / (sqrt(n))) isn't equal o(n2).


Comments

Popular posts from this blog

python - TypeError: start must be a integer -

c# - DevExpress RepositoryItemComboBox BackColor property ignored -

django - Creating multiple model instances in DRF3 -