c - empirical run-time analysis

Question

hey so im having a bit of a hard time grasping empirical run-time analysis. so i have this question:

Suppose we have an O(1) function that took 8s to execute with n = 2,000. What would you expect the runtime to be if n = 10,000?

now here's my thought process which i believe is wrong: if T(n) is O(1) then T(n) = c * O(1) where c is just some constant. so solving for c we get c = T(n) / O(1). now since we know T(2000) = 8s and that n = 2000 we can just plug that in to solve for c, c = (8s) / (2000) which gives us 0.004. Now we have to the the same for n = 10,000 so in this case T(10,000)= c * O(1) in this case we can just plug in the same c we found earlier since it just a constant, and plug in 10,000 for O(1) which would gives us T(10,000) = (0.004) * 10,000 which equals 40s. im just not sure if my thought process was right on this one.

Answer 1

The correct answer is that we could not expect any particular time.

To say a function’s run-time O(1) is to say there is some number C such that the function always runs in less than C seconds. If the function ran in 8 s once, we know C is at least 8. But it could be a million. Or a septillion.

What O(1) does tell us is that the run time is limited regardless of what n is. That run time could go up and down with various n, but it is always limited by C.

In contrast, compare this to a function with run-time O(n). This means there is a number C such that the function’s run-time is always less than C*n seconds (except a finite number of exceptions are allowed). So we do not have a constant limit; we have a limit that depends on n. This function might take more and more time as n grows.

Or it might not. The O notation only tells you a limit on a function’s run-time. It does not tell you the actual run-time. If I know you had a gallon of gas in your car yesterday, and you went 30 miles, I know your car gets at least 30 miles per gallon. If you have two gallons in it today, I know you could go at least 60 miles, but maybe you could go more, and I do not know how far you will actually go. I know there is a limit on your travel, but I do not know what it actually is or how far you will go.

Answer 2

More often than not the problem with big-O notation is informal (not to say sloppy) notation that carries along a lot of assumption.

First of all, the Ο symbol¹ expects a function between its parenthesis, so a notation like Ο(1) is unclear at first (since 1 is a number).
It is customary in some area of math to denote with "1" the function f:ℕ→ℕ defined as f(n) = 1 ∀n ∊ ℕ.
This is just a function returning 1 for every input².

Another point to consider is that the Ο as defined classically operates on single-variable functions and to avoid ambiguity the independent variable of the two function should always be explicitly written.
However often this is not done since it is clear from the context that we are dealing with a specific kind of functions only.

For the sake of the reader alertness and at the cost of a cumbersome notation I'll not drop the independent variables thereby writing Ο(1) as Ο(1(n)).

Finally, I prefer the notation f(n) ∊ Ο(1(n)) over the common one that uses an equal sign.

---

We have hopefully clarified that with the notation f(n) ∊ Ο(1(n)) we are asserting a property of a function f(n) w.r.t. another function that returns 1 for every input.

The big-O notation is a shorthand (just like the limit notation) that in our specific case translates to

f(n) ∊ Ο(1(n))

          ∃N ∊ ℕ: ∀n > N |f(n)| ≤ M · |1(n)|     (by definition)
          ∃N ∊ ℕ: ∀n > N |f(n)| ≤ M · 1(n)       (1(n) always positive)
          ∃N ∊ ℕ: ∀n > N |f(n)| ≤ M · 1           (1(n) = 1 for all n)
          ∃N ∊ ℕ: ∀n > N |f(n)| ≤ M                

So the notation simplifies to f(n) being bounded in absolute value by an (unspecified!) constants M.

This leaves us with a lot of functions, even given the value of the function at a point.
For example, even if we know that f(2000) = 8, the two functions g(n) = 8 cos(n-2000) and h(n) = 8 e^n-2000 both are in Ο(1(n)) but their value at n = 10000 differs!

---

The big-O notation is useful because it simplifies things but so far it seems that it failed by a great length.

The missing piece is that we are dealing with algorithms and their time-complexity³ so the functions f that we are interested in are:

• Non-piecewise.
  We consider a piecewise function as arising from two algorithms rather than the expression of a single algorithm.

• Monotonic non-decreasing. We assume that for the same problem, a bigger instance is lengthier (in time) to solve.

Under this assumptions, we can see that if a function is bounded then at some point it must cease to increase and stay at that value indefinitely.

This is what the f(n) ∊ Ο(1(n)) notation expresses: f is a constant function (asymptotically).

If f is constant then f(n) = c and if f(2000) = 8 then c = 8 and thus f(10000) = 8.

At its best the big-O notation is used as follow: take the function between the Ο's parenthesis, multiply it by a constant c and use it in place of f.

Sometimes we don't even care about constants: Ο(1(n)) means that if we double n the output stays the same, Ο(n) means that if we double n the output doubles (n is 2 for n = 2), Ο(n²) means that if we double n the output quadruples (n² is 4 for n = 2) and so on.

---

The problem with your approach is two-fold: saying that T(n) = c * O(1) is correct but useless, we made no progress forward since all we are saying is that T(n) is constant multiplied by another constant (remember that O(1) is a constant function) and thus it is a constant.
The other mistake is substituting O(1) with n to get the value of c.
O(1) is a set of functions and even if we write it as c' (meaning all the possible constants) this is not n! n is the input value, the size of the encoding of the problem instance while c' is an arbitrary constant.

This is the whole point of constant functions: they do not depend on the input, they are arbitrary in this regard if you wish.

---

¹ It is not an operator in the strict sense. If we focus our attention to functions defined on a set C and C-valued (e.g. f ∊ C→C) then Ο maps a C→C function to a set of C→C functions (e.g. Ο:(C→C)→℘(C→C)) and thus is not a map from and to the same set.

² The notation is intentionally fuzzy to let the mathematician use it in different contexts; we used it for natural valued sequences but it can be extended to any set and to the meaning of returning the "unity" of any context-implied algebraic structure.

³ Please beware that run-time is a very very misleading term!