Costs. Algorithm analysis. Algorithms in

Question

It is possible to state that the cost of an O(n²) algorithm will always be less than a cost of O(n). Comment on the truth of the statement:

For an O(x) algorithm, the complexity (e.g. time or space complexity) grows like x. Maybe in your case it helps to draw the two functions f(n) = n² and g(n) = n and then derive if the statement is true or not? — Michael Kreutz
– Michael Kreutz, Commented May 5, 2020 at 20:14

Daniel · Accepted Answer · 2020-05-05 22:16:34Z

1

No. Saying that an algorithm is O(n²) means that there is at least a case where the algorithm will take a quadratic number of operations to finish.

In a O(n) algorithm, the worst case will be linear, so for a big enough input, the worst case of a O(n²) algorithm will always take more operations than a O(n) algorithm.

O(n) = k * n + a
O(n²) = k2 * n² + k1 * n + b

so we wanna prove that there is a case that O(n) < O(n²)

k * n + a < k2 * n² + k1 * n + b
(k - k1) * n + (a - b) < k2 * n²
(k - k1) / k2 + (a - b) / (k2 * n) < n

We can see that, as n grows, the constants in the left side will stay the same or decrease, so there will be a point where O(n) < O(n²).

edited May 5, 2020 at 22:16

answered May 5, 2020 at 21:14

Daniel

7,8009 gold badges37 silver badges108 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Costs. Algorithm analysis. Algorithms in

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related