We know thah O(n) + O(n) = O(n) for this, even that O(n) + O(n) + ... + O(n) = O(n^2) for this.
But what happend if O(n) + O(n^2)?
Is O(n) or O(n^2)?
Asked
Active
Viewed 75 times
0
-
1Answer: ... yes – Tim Biegeleisen Sep 18 '22 at 06:08
-
It would be `O(n^2+n)`. Constants are dropped, but factors involving `n` should stay. – Tim Roberts Sep 18 '22 at 06:08
-
O(n²) is far larger than O(n) so obviously O(n + n²) can't be O(n) – phuclv Sep 18 '22 at 06:10
-
1@TimRoberts `O(n^2+n)` is equal to `O(n^2)`. – kaya3 Sep 18 '22 at 06:15
1 Answers
0
The Big O notation (https://en.wikipedia.org/wiki/Big_O_notation) is used to understand the limit of a specific algorithm, and how fast its complexity grows. Therefore when considering the growth of a linear and a quadratic component of an algorithm, what remains in Big I notation is only the quadratic component.
As you can see from the attached image, the quadratic curve grows much faster (over y-axis) than the linear curve, determining the general tendency of the complexity for that algorithm to be just influenced by the quadratic curve, hence O(n^2).
The case for O(n) + O(n) = O(n) it's due to the fact that any constant in Big O notation can be discarded: in fact the curve y = n and y = 2n would be growing just as fast (although with a different slope).
The case for O(n) + ... + O(n) = O(n^2) it's not generally true! For this case the actual complexity would be polynomial with O(k*n). Only if the parameter k equals to the size of your input n, then you will end up with a specific quadratic case.
gifa
- 86
- 5