Yes, that's correct. If runtime is the sum of several runtimes, by order of magnitude, the largest order of magnitude dominates.
Algorithm domination
-
06-10-2022 - |
Question
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?
La solution 2
Autres conseils
[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).
Assuming that big-O notation is used in the sense of asymptotic tight bound
, which really should be denoted with a big-Theta, then I would answer C), because Theta(n) = Theta(n + log(n))
. (Because log(n)
is dominated by n
).
If I am formally (mathematically) correct, then I would say that none of these answers is correct, because O(n)
and O(n+log(n))
only give upper bounds, but not lower bounds on the asymptotic behaviour:
Let f(n) in O(n)
and g(n) in O(n + log(n))
. Then there are the following contra examples:
For A): Let f(n) = n
in O(n)
and g(n) = 1
in O(n + log(n))
. Then g(n)
does not dominate f(n)
.
for B): Let f(n) = 1
in O(n)
and g(n) = n
in O(n + log(n))
. Then f(n)
does not dominate g(n)
.
for C): Let f(n) = 1
in O(n)
and g(n) = n
in O(n + log(n))
. Then g(n)
does dominate f(n)
.
As this would be a very tricky question, I assume that you use the more common sloppy definition, which would give the answer C). (But you might want to check your definitions for big-O
).
If my answer confuses you, then you probably didn't use the formal definition and you should probably ignore my answer...