Ben Bacarisse wrote:
> Give me a few values for f(n) (just list them: f(0) = ?, f(6) = ? and so
> on) for which you can be *certain* than f is not O(n^2).
>
> You seem to be saying that f(5) = 125, f(6) =
> 808281277464764060643139600456536293376 means that f can't be O(n^2) but
> that's not so. You can no idea what happens for n > 6. f might even be
> O(1).
Difference across machines and the same machine of course can occur, but that doesn't prevent one from comparing the quality of an algorithm against another nor against itself when modified.
If I called f(5) over and over it wouldn't be guaranteed to take the same amount of time/memory to return an answer.
f(5) ran 5 times could be {10ms, 15ms, 12ms, 14ms, 1hour}
f(6) could be {15ms, 17ms, 12ms, 18ms, 16ms}
f(100): {107ms, 125ms, 120ms, 150ms, 135ms}
and so on. Given sufficient runs and sufficient inputs you *COULD* derive the trend of the function and assign it a categorization. But you don't have to as this analytical framework exists to eliminate such a dependency on a machine and on limited inputs.
Determining the category of a function is accomplished by evaluating it's components. For instance:
"primitive" operations are considered O(1); In other words 1-step
These include: assignment, calls, arithmetic, index lookups, reference lookups, and a few others. So if I had a function "arrayMax" I could determine it's categorization as follows:
var intList = [8,6,7,15,5,3,0,9]
var arrayMax = (xs, n) =>
n == 1 ? xs[0] :
Math.max(arrayMax(xs, n - 1),xs[n - 1]);
arrayMax(intList, intList.length)
///////////
when n == 1 the runtime is 3 // comparison + lookup + return
else it's the runtime of n - 1 for the recursive call + 7 primitives
or for clarity where T(n) is the runtime:
T(n) = 3, if n == 1
T(n) = T(n - 1) + 7, otherwise
in closed form: T(n) = 7(n - 1) + 3 = 7n - 4
So I'm claiming that 7n - 4 is O(n)
How do I prove it? I simply have to be consistent with the definition of O(n). So I'll "fill in the blanks and turn the crank"
Definition:
f(n) is O(g(n)), for f(n) <= c*g(n) where n >= n0
f(n) := arrayMax
g(n) := n
//7n - 4 <= c*n forAll n >= n0, so :
c := 7
n0 := 1
FIN.
instances of the proof:
var f = n => 7 * n - 4
var g = n => n
f(1) <= 7 * g(1) //true
f(2) <= 7 * g(2) //true
f(3) <= 7 * g(3) //true
...
f(4000) <= 7 * g(4000)
...
etc.
The above was only about evaluating time, but a similar approach is applied for space analysis.
If this doesn't help, then I still don't understand where we missing each other