f（n）是Ω（g（n）），Θ（g（n））还是O（g（n））？

Question

Given two functions in PHP, say

function f($n) {
    return $n;
}

function g($n) {
    return pow($n, (2/3));
}

How to check if a function f(n) is in Ω(g(n)), Θ(g(n)) or O(g(n)) in PHP?

What I tried so far:

$n = INF;

$A = f($n) / g($n);

if ($A == 0) {
    echo "f(n) = O(g(n))";
} elseif (is_infinite($A)) {
    echo "f(n) = Ω(g(n))";
} elseif ($A != 0) {
    echo "f(n) = Θ(g(n))";
}

Shouldn't that work?

Answer 1

Your basic idea is correct: you have to find the limit of f(n)/g(n) as n grows without bound. Unfortunately there is no easy way to compute the exact limit in PHP, since that requires symbolic computations which is best left to a computer algebra system such as Mathematica or Maxima.

You can approximate the limit by computing f(n)/g(n) for increasing values of n and seeing if you get a sequence that approaches a fixed value. For example:

$n=1;
while ($n < 1e300) {
    $A = f($n)/g($n);
    echo $A, "
";
    $n *= 1e12;
}

In this particular case the sequence of f(n)/g(n) seems to grow without bound, so the numerical evidence suggests that f(n) is in Ω(g(n)). This is not a proof though; symbolic methods are needed for that.