With O(n) known and system clock known, can we calculate the execution time of the code

Question

The time complexity of the code is known. The system on which the program was executed is Intel Corei3 which is dual core and CPU @ 2.4ghz — it has 4 logical processors. With these details, how can the execution time of the code be calculated?

public class PerfmTest {
    public static void main(String[] args) {
      getexeTime(1000000);
    }

    public static void getTime (long n) {
      // long startTime = System.currentTimeMillis();
      long startTime = System.nanoTime();
      long k = 0;
      for (int i = 1; i <=5; i++) {
          // k = k + 5;
      }
      // long endTime = System.currentTimeMillis();
      long estimatedTime = System.nanoTime() - startTime;
      //System.out.println("Execution time for n = " + n + " is " + (endTime - startTime) + " milliseconds");
      System.out.println("Execution time for n = " + n + " is " + estimatedTime + " nanoseconds");
    }
 }

The output was 855 nanoseconds.

I'm guessing you didn't know that code without observable side-effects can be optimized at compile time. Regardless, what **are** you trying to achieve with this exercise? — Elliott Frisch, Nov 15 '16 at 01:43
I am aware that code is optimized. But point is how in theory its O(n) and how does it work with 2 dual cores. I work on a teaching aid project. — DBlearner, Nov 15 '16 at 01:46
In theory, it isn't O(n) because the compiler can eliminate the loop (you never read `k` after the loop - so there are no side-effects to removing it - even if you put the addition in - in theory). Thus, your current code is, in theory, `O(1)`. Also, beware micro-benchmarks. There is a JIT, and cold runs are different from warm runs (and it may take multiple runs to trigger JIT). — Elliott Frisch, Nov 15 '16 at 01:52
@Elliot Yes its O(1) therefore a constant time, agreed. So if it was loop with n times its difficult to predict is your point (ie., warm and cold runs) right? — DBlearner, Nov 15 '16 at 03:49

nhouser9 · Accepted Answer · 2016-11-15T02:47:33.320

1

If I understand you correctly, you are asking if we can calculate running time by knowing system specs and the code in question. The answer to this is no, we cannot calculate the execution time.

The reason is that the code is not run in isolation. Those four processors are not only running your code. The operating system is doing things in the background, services are running, and so on.

In fact, not only can we not calculate the running time of the code, but we cannot even predict future running times if we already know the running time. Anything might happen during a second run of the code that could change the output. More context switches, more background tasks, or anything else.

I have experienced these effects firsthand many times when running performance tests. The same test suite will produce different timings if the computer has been sitting idle for longer, or if the last boot was a cold boot as opposed to a standby / resume, etc.

If you are asking about how to measure the running time of your code, all of the above still apply. You are talking, in essence, about running an experiment. In an experiment, all external variables must be controlled. The system must be in the same state for each run of the test, which is technically possible to achieve, but certainly far beyond the scope of this question.

The only thing we can do with any reasonable expectation of success is predict that algorithm A will perform better than algorithm B (and even that will sometimes yield unexpected results for different inputs, input sizes, etc.). We cannot predict exactly how long algorithm A will take.

Summary

Without an extremely controlled environment (beyond the scope of this question) it is impossible to calculate, estimate, or even measure the running time of an arbitrary piece of code.

edited Nov 15 '16 at 02:47

answered Nov 15 '16 at 01:43

nhouser9

6,730
3
21
42

I think you could make a no-strings-attached timing estimate of algorithms though if you know the complexity and can reasonably estimate the processing time per iteration. – Bohemian Nov 15 '16 at 02:12
1

@Bohemian We can make very good estimates of algorithms relative to one another - I definitely agree with that. We cannot make very good estimates at all of absolute timings, precisely because we cannot reasonably estimate the processing time per iteration. It will vary with compiler, hardware, system state, software, and many additional factors; moreover, those variations will often be non-trivial. That's just my experience as a professional performance analyst. – nhouser9 Nov 15 '16 at 02:19
@ Nhouser9 , so the gist is that only used for comparison. – DBlearner Nov 15 '16 at 03:59
@Uma right. we can't guess exact times but we can tell one method is better than another method – nhouser9 Nov 15 '16 at 04:06
@nhouser9 well, I *can* estimate times. I know the approximate processing duration of most basic operations and I can "guestimate" within an order of magnitude of the actual timings. Over the years I have timed and remembered how long simple operations take and experience fills in the rest. It's a bit like a cost estimating technique I heard of whereby you estimate the *weight* of each type of hardware that comprises a military vehicle (electronics, armour, drive train, etc) and multiply each by type by its "cost density" to arrive at a total cost, which is as they say "close enough for jazz". – Bohemian Nov 15 '16 at 14:26
The answer is no, but not for the reason given here. It is impossible *in principle* because the *O(N)* expression doesn't contain sufficient information. – user207421 Nov 15 '16 at 21:55
@EJP if you are assuming OP is talking about a piece of code in general, sure. To me his question reads like he is talking about **this specific** piece of code, in which case my answer responds most adequately to the question. – nhouser9 Nov 15 '16 at 22:04

score -1 · Answer 2 · edited Dec 15 '16 at 00:23

-1

With O(n) known and system clock known, can we calculate the execution time of the code.

No. O(N) only means that the execution time grows linearly with N, i.e. via a linear equation of the form

t = aN+b

where y is the time, N is N, and a and b are constants, but it doesn't tell you the constants.

edited Dec 15 '16 at 00:23

Jonathan Leffler

730,956
141
904
1,278

answered Nov 15 '16 at 02:31

user207421

305,947
44
307
483

Got the picture of O(n) that we cannot compute the execution time. – DBlearner Nov 15 '16 at 04:03
I cannot mark two solutions the site says though I wanted to mark it as solution. – DBlearner Nov 15 '16 at 04:07
If I may say so, I consider this a better answer than the other, as it addresses your fallacy at its root. The other assumes it is possible in principle, but gives reasons why not in practice: in other words he shares your fallacy. – user207421 Nov 15 '16 at 21:46
@EJP Look at OP's code. They are trying to measure its running time: `long estimatedTime = System.nanoTime() - startTime;`. Note also that the question does not say "can we calculate the execution time of an unknown piece of code", it says "can we calculate the execution time of the code", which also indicates that OP wants to know about the code in the post. Your answer misunderstands the question; you think OP wants to calculate running time of unknown code. OP actually wants to calculate running time of known code, in which case my answer is more appropriate. – nhouser9 Nov 15 '16 at 22:10
@nhouser Look at my answer. You cannot go from an algorithmc complexity notation to an execution time because it doesn't contain all the information, regardless of the code, the CPU, the configuration, the weather, the phase of the moon. This is an *a priori* truth: it doesn't depend on any external facts whatsoever. – user207421 Nov 16 '16 at 00:32
@EJP I know you can't. You're missing the point. The OP is not asking if you can go from O(n) to execution time. The OP is asking if you can go from O(n) **and the code in question** to execution time. That's why your answer doesn't fit. – nhouser9 Nov 16 '16 at 00:34
@nhouser9 You are missing the point. I am addressing the question expressed in his title, and specifically quoted in my answer. As a matter of fact the question doesn't make much sense. He has a variable called 'estimatedTime' which is actually *measured* time for example. – user207421 Nov 16 '16 at 00:51
@EJP He asks "can we calculate the execution time of **the code**". I think it is very reasonable to assume that by **The code** he means **The code posted below**. I will state, for the final time, that you have misinterpreted the question. Not only was my interpretation of the question correct, it also makes a lot more sense. You assume that by **the code**, OP means **any unknown code**, which is a much bigger and stranger logical leap than what he actually meant: **the code posted below**. – nhouser9 Nov 16 '16 at 00:55

With O(n) known and system clock known, can we calculate the execution time of the code

2 Answers2

Linked