CODEWITHSUNDEEP
algorithmcomplexity-theoryperformanceprocessing-efficiency
aceBox
aceBox

Reputation: 731

Estimation of program execution time from complexity

I want to know, how i can estimate the time that my program will take to execute on my machine (for example a 2.5 Ghz machine), if i have an estimation of its worst case time complexity? For Example : - If I have a program which is O(n^2), in worst case, and n<100000, how can i know /estimate before writing the actual program/procedure, the time that it will take to execute in seconds?

Wouldn't it be good to know how a program actually performs, and it will also save writing code which eventually turns out to be inefficient! Help greatly appreciated.

Upvotes: 1

Views: 3375

Answers (3)

C-Otto
C-Otto

Reputation: 5843

Instead of dealing with complecity, you might want to have a look at Worst Case Execution Time (WCET). This area of research most likely corresponds to what you are looking for.

http://en.wikipedia.org/wiki/Worst-case_execution_time

Upvotes: 0

argentage
argentage

Reputation: 2778

Since big O complexity ignores linear coefficients and smaller terms, it is impossible to estimate the performance of an algorithm given only its big o complexity.

In fact, for any specific N, you cannot predict which of two given algorithms will execute faster.

For example, O(N) is not always faster than O(N*N) since an algorithm that takes 100000000*n steps is O(N) is slower than an algorithm than takes N*N steps for many small values of N.

These linear coefficients and asymptotically smaller terms vary from platform to platform and even amongst algorithms of the same equivalence class (in terms of big O measure). 3

The problem you are trying to use big O notation for is not the one it is designed to solve.

Upvotes: 4

maniek
maniek

Reputation: 7307

Multiply N^2 by the time You spend in an iteration of the innermost loop, and You have a ballpark estimate.

Upvotes: -1

Related Questions