R and f are completely different functions that have nothing in common except how they grow relative to n, so there is no reason why f(n) should equal R(n). R is "the amount of resources the process requires for a problem of size n". f is an unrelated mathematical function.
What makes the definition of Θ particularly confusing is that it doesn't refer to the resource is R is measuring nor the process that is using the resource.
Examples of R(n) could be:
- Number of registers used in summing n numbers.
- Disk used to transcode n GB of video
- Time taken to launch n drones.
But the definition of Θ doesn't mention resources (registers, disk, time), nor processes (summing, transcoding or launching).
If our 'process' is a software procedure called p, then we have three quite different 'functions':
p(n) - a procedural function that programmers work with.
R(n) - a measuring function like ones used by engineers.
f(n) – a 'pure' mathematical function.
If we use the factorial procedure as an example, which has Θ(n) growth with respect to time, we would have:
p(n) = (define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))
R(n) = The time in seconds for (factorial n) to complete.
f(n) = n
R(n) = f(n) implies (factorial 17) takes exactly 17 seconds to run, which is unlikely.
The definition of Θ(n) is saying k₁ and k₂ exist so that once n is big enough:
k₁ * n <= "Time taken for (factorial n) to run in seconds" <= k₂ * n
On a modern computer k₁ would need to be very small for k₁ * n to be less than the actual running time.
For the tree-recursive Fibonacci procedure growth is Θ(1.618ⁿ) so we have:
p(n) = (define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else ... )))
R(n) = The time in seconds for (fib n) to complete.
f(n) = 1.618ⁿ
and the definition is saying k₁ and k₂ exist so that:
k₁ * 1.618ⁿ <= "Time taken for (fib n) to run" <= k₂ * 1.618ⁿ)
(I've used "1.618" for the golden ration instead of "φ")
