How do I derive and equation for Big O notation For example

How do I derive and equation for Big O notation? For example, if the algorithm is O(N^3) and it takes 5 seconds to sort an array of size 1000, how long would it take to sort 3000?

Solution

Given algorithm complexity is O(N^3) it is upper bound..

for input size n =1000, it takes 5 seconds to sort the array..

means in 5 secs the total operations performed are N^3 = (1000)^3= 10^6 operations.

In 5 seconds the will perform 10^6 operations

Now the time taken to sort N =3000 elements..

To sort 3000 elements, the algorithm will perform N^3 = (3000)^3 operations= 27*(10^6) operations..

The time taken to perform 27*(10^6) operations is:

10^6 operations algorithm needs 5 sec..

for 27*(10^6) operations algorithm needs 27*5 = 135 seconds.

answer is 135 seconds to sort 3000 elements..