-1

n2 has a lower order of growth than n3. I get it that we can verify it graphically or we can put values like 1,2,3... n3 attains a value in less time than n2, then why do we prefer n2 of n3?

coder_404
  • 5
  • 1
  • 5
  • What does "better" mean to you and what is the context? For the context of time or space complexity, "better" most definitely should not mean "grows faster" (the opposite, in fact). – Bernhard Barker Sep 19 '17 at 17:22

2 Answers2

2

n3 attains a value in less time than n2

n^3 does indeed attain a value on the Y axis in less space on the X axis than n^2. But what is that value it's attaining? What do these axes represent? Let's look at an actual graph of this:

enter image description here

(In this graph, O(n^3) would be a curve between O(2^n) and O(n^2).)

The Y axis is operations, not results. And the X axis is elements, not time. So your O(n^3) algorithm is going to perform more operations. In every case the results are the same. The metric being measured here is how many operations are performed on a given set of elements in order to achieve the result.

n^3 climbs the graph faster than n^2, which means it performs more operations to compute the same results. More operations on the same hardware means it takes more time.

We prefer O(n^2) algorithms over O(n^3) algorithms because we prefer algorithms which calculate the same results with fewer operations.

David
  • 208,112
  • 36
  • 198
  • 279
0

Because you are measuring use of resources (time or space), which are costs, not performances, so lower is better

Luca C.
  • 11,714
  • 1
  • 86
  • 77