Prediction Model for Measurement-Based Timing Analysis, In Proc. of 6th ACM International Conference on Software and Computer Applications, pp. 9-14, Thailand, 2017. https://dl.acm.org/citation.cfm?id=3056666

Actually, program execution time does not only depend on the number of instructions or purely the performance of the machine. The type and mix of instructions, computational paths they go through, and their behaviour affects the total execution time.

Some instructions take one cycle to execute, others two, few will take multiple cycles (i.e. division instructions). Branch instructions and branch prediction hardware highly affect the execution time (whether the branch has been taken or not), predictor hit or miss. This will entail a pipeline flush and fetching new instructions thus more time. Caching and cache replacement policies add to the complexity. This is even more so when multicore platforms are used. Bus contention, shared resources and cache interference affect the total task/program execution time. This is of course also dependent on the task load (CPU or memory bound).

Taking these into account, it is hard (if not impossible) to have a prediction model accurate enough especially for modern complex hardware. However, there are techniques used within the real-time community to find Worst Case Execution Time estimates (WCET) that are both tight (close to the actual observed worst case) and safe (never less than the actual observed worst case). These techniques fall under three categories:

1. Static Analysis: closest to what you seek. Given the assembly/machine code, a flow path model, a timing model, and a hardware model, these tools give WCET estimates by analyzing the worst case execution path the program will go through. Pros: mostly tight estimates, used in industry. Cons: requires understanding of the code, requires extensive inputs vectors for testing, needs code annotations to guide the tool, mostly restricted to single core platforms, commercial and expensive (aiT, RapiTime, OTAWA .. etc), support for popular CPUs and microcontrollers.

2. Measurement based: Basically you run your code with various input sequences and record the timing (through HW performance counters or flags and oscilloscopes/logic analyzers), the standard practice is to add 10% to 20% more time to the worst observed execution time. Pros: Easier than static analysis but still requires lots of inputs and trials, also used in some industrial and commercial developments

3. Probabilistic techniques (either static or measurement based), for example, the MBPTA (measurement based probabilistic timing analysis) takes similar measurements like the approach above (requires much less experimentation though) and applies probabilistic approaches to find WCET estimates. For example, extreme value theory (EVT). Probabilistic techniques are still new, quite promising, possibly good for multicores, still undergoing research and validation, however, studies vary on how tight the estimates are to the true worst case execution time (mixed results depending on technique used and platform). It is basically the new child in the block that researchers are still studying!

Big(O) notation has nothing to do with estimating actual execution times. It is merely a measure of how complex the code or algorithm is and how the compexity scales with the number of various inputs (polynomial time complexity, logarithmic, exponential ... etc). It helps in comparing the efficency of different solutions to one problem, that is all.