Calculate exact runtime (time complexity) given recursive functions

Question

Considering this code which calculates a power of a double x:

public static double F1 (double x, int k){
    if (k==1) { return x; } // O(1)
    return x * F1(x, k-1);  // O(k)
}

I have concluded that

• the nr of operations in if (k==1) { return x; } : 2 operations, the if-statement and the return-statement. Thus, T(1) = 2

• the nr of operations in return x * F1(x, k-1); : 4 operations, the return-statement = 1, the *-operator = 1, and F1(x, k-1); = 2. So the first part of the equation = 4

• We have one recursive call in x * F1(x, k-1), so x = 1.

• We reduce the problem by 1 in each recursive call, so y = k-1. So the second part of the equation = T(k-1)

Putting this all together, we get:

4 + T(k-1), T(1) = 2

But how do I proceed from here to find the exact runtime?

I tried to look at this question for an explanation, but it focused on how to calculate the Big-O notation, and not the exact time complexity. How do I proceed to find the exact time-complexity?

The answer here should be:

Exact: 4k-2 
Tilde: 4k 
Big-O: O(k)

But I don't know what they did to arrive at this.

Answer 1

But how do I proceed from here to find the exact runtime?

You toss everything you did so far in the garbage and fire up JMH instead, see later for more on that.

It is completely impossible to determine exact runtime based on such academic analysis. Exact runtime depends on which song is playing in your music player, whether your OS is busy doing some disk cleanup, sending a ping to the network time server, which pages so happen to be on the on-die caches, which CPU core your code ends up being run on, and the phase of the moon.

Let me say this as clear as I can: Something like 4k - 2 is utterly irrelevant and misguided - that's just not how computers work. You can't say that an algorithm with 'exact runtime' 4k - 2 will be faster than a 6k + 2 algorithm. It is equally likely to be slower: It holds zero predictive power. It's a completely pointless 'calculation'. It means nothing. There's a reason big-O notation exist: That does mean something regardless of hardware vagary: Given 2 algorithms such that one has a 'better' big-O notation than the other, then there exists some input size such that the better algorithm WILL be faster, regardless of hardware concerns. It might be a really big number and big-O does nothing whatsoever to tell you at what number this occurs.

The point of big-O notation is that it dictates with mathematical certainty what will eventually happen if you change the size of the input to your algorithm, in very broad strokes. It is why you remove all constants and everything but the largest factor when showing a big-O notation.

Take a graph; on the X-axis, there's 'input size', which is the 'k' in O(k). On the Y-axis, there's execution time (or if you prefer, max. memory load). Then, make up some input size and run your algorithm a few times. Average the result, and place a dot on that graph. For example, if you are running your algorithm on an input of k=5, and it takes 27ms on average, put a dot on x=5, y=27.

Keep going. Lots of dots. Eventually those dots form a graph. The graph will, near the x=0 point, be all over the place. As if a drunk with a penchant for randomness is tossing darts at a board.

But, eventually (and when 'eventually' kicks in is impossible to determine, as, again, it depends on so many OS things, don't bother attempting to predict such things), it'll start looking like a recognizable shape. We define these shapes in terms of simplistic formulas. For example, if it eventually (far enough to the right) coalesces into something that looks like what you'd get if you graph y=x^2, then we call that O(x^2).

Now, y=5x^2 looks exactly like y=x^2. For that matter, y=158*x^2 + 25000x + 2134931239, if you look far enough to the right on that curve, looks exactly like y=x^2. Hence why O(158x^2+20x) is completely missing the point, and therefore incorrect. The point of O is merely to tell you what it'll look like 'far enough to the right'.

This leaves us with precisely 2 useful performance metrics:

1. O(k) notation. Which you correctly determined here: This algorithm has an O(k) runtime.

2. A timing report. There is no point trying to figure this out by looking at the code, you need to run the code. Repeatedly, with all sorts of guards around it to ensure that hotspot optimization isn't eliminating your code completely, re-running lots of times to get a good average, and ensuring that we're past the JVM's JIT step. You use JMH to do this, and note that the result of JMH, naturally, depends on the hardware you run it on, and that's because programs can have wildly different performance characteristics depending on hardware.

Answer 2

For the first k-1 steps you execute:

1. the comparison k==1
2. the subtraction k-1
3. the product x * ...
4. the return instruction

In the last step you execute:

1. the comparison k==1
2. the return instruction

So you have 4*(k-1)+2 = 4k-2 overall instructions.

EDIT: As @rzwitserloot correctly pointed out, the quantity that you are searching for is not very significant, but it depends on how the code is compiled and executed. Above I've just tried to figure out what your teacher meant with "exact time-complexity".