All geek questions in one place

Trust in the algorithm

Studying the test and getting this question:

Comparing two algorithms with asymptotic complexities O(n) and O(n + log(n)), 
which one of the following is true?

A) O(n + log(n)) dominates O(n)
B) O(n) dominates O(n + log(n))
C) Neither algorithm dominates the other.

O (n) correctly dominates log (n)? So, in this, we simply take o (n) from both and do not derive any of them?

+4
source share
3 answers

Yes, it is right. If the execution time is the sum of several time periods, the largest order dominates by an order of magnitude.

+1
source

[C] true, due to the Big-O summation property

Summation 
O (f (n)) + O (g (n)) -> O (max (f (n), g (n))) 
For example: O (n ^ 2) + O (n) = O (n ^ 2)

At Big-O, you only care about the biggest growth function and ignore all the other supplements.

: [A] , [A].

O(n) ~ O(n + log(n))      <=>
O(n) ~ O(n) + O(log(n))   <=>
O(n) ~ O(n).
+3

, big-O asymptotic tight bound, , C), Theta(n) = Theta(n + log(n)). ( log(n) n).

() , , , O(n) O(n+log(n)) , :

f(n) in O(n) g(n) in O(n + log(n)). :

A): f(n) = n O(n) g(n) = 1 O(n + log(n)). g(n) f(n).

B): f(n) = 1 O(n) g(n) = n O(n + log(n)). f(n) g(n).

C): f(n) = 1 O(n) g(n) = n O(n + log(n)). g(n) f(n).

, , sloppy, C). ( big-O).

, , , , , , ...

+1

Source: https://habr.com/ru/post/1525131/

More articles:


All Articles