Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithm domination

Studying for a 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) dominates log(n) correct? So in this do we just take o(n) from both and deduce neither dominate?

like image 696
Deekor Avatar asked May 13 '26 05:05

Deekor


2 Answers

[C] is true, because of the summation property of Big-O

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

In Big-O, you only care about the largest-growing function and ignore all the other additives.

Edit: originally I put [A] as an answer, I just didn't put much attention to all the options and misinterpreted the [A] option. Here is more formal proof

O(n) ~ O(n + log(n))      <=>
O(n) ~ O(n) + O(log(n))   <=>
O(n) ~ O(n).
like image 130
oleksii Avatar answered May 15 '26 23:05

oleksii


Yes, that's correct. If runtime is the sum of several runtimes, by order of magnitude, the largest order of magnitude dominates.

like image 28
La-comadreja Avatar answered May 15 '26 23:05

La-comadreja



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!