CODEWITHSUNDEEP
algorithmtime-complexity
Katrina
Katrina

Reputation: 47

How can we calculate running time of an algorithm using the asymptotic complexity?

If we are given the complexity of a certain algorithm, what the procedure to calculate the running time for N^3.

Upvotes: 0

Views: 105

Answers (1)

Kyborek
Kyborek

Reputation: 1511

There are two ways to deal with this issue:

  1. Incremental

We need to recalculate from n=50 to n=300 which is 6 times larger n. Given the complexity θ(n³) 6 times larger will result in 216 (6³) times longer running time. This gives us t=2160s for n=300

  1. Absolute

The running time is some unknown constant x multiplied by the complexity n³. to find out the x we solve this equation: t=x*n³ or rather 10=x*125000 which will give us final result of x=1/12500 Now we need to find new time for new n t=(1/12500)*300³ which simplifies to t=60*12*3 which gives us the same result of 2160 seconds.

Upvotes: 1

Related Questions