Search code examples
algorithmdata-structuresanalysis

if n^3 has a fast rate of growth than n^2 i.e. O(n^2)<O(n^3) then why is n^2 better than n^3?

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?

Solution

  • 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.