0

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?

8
  • What do you mean by *function f(n) is in Ω(g(n)), Θ(g(n)) or O(g(n)) *? The f($n) / g($n) just divide the result of each function
    – Javad
    Mar 14, 2014 at 21:56
  • 3
    PHP isn't a symbolic math engine. Consider using Mathematica instead.
    – p.s.w.g
    Mar 14, 2014 at 21:56
  • Maybe I did it in the wrong way, but I want to know whether f(n) is asymptotically bounded by g(n) by given constants. That is what I mean, when I ask whether f(n) is in Ω(g(n)), Θ(g(n)) or O(g(n)). In this specific example, I mean: The program should decide whether n is in Ω(n^(2/3)), Θ(n^(2/3)) or O(n^(2/3)). Mar 14, 2014 at 22:00
  • @p.s.w.g - maybe Mathematica is better, but if I want to do it in PHP, do you think there is a way? Mar 14, 2014 at 22:01
  • 1
    Big-O is not even about the range of the function, it's about the complexity of the algorithm for computing it.
    – Barmar
    Mar 14, 2014 at 22:04

2 Answers 2

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";
    $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.

-1

Both the time and space requirements for both f() and g() are in Ω(1), Θ(1) and O(1).

3
  • Really? How can a function depending on a variable be constant? Mar 14, 2014 at 22:23
  • Please read about Big-O notation here. en.wikipedia.org/wiki/Big_O_notation The general idea of Big-O, as mentioned in a comment above, is to characterize the running time (or memory usage) of an algorithm. Both of your functions have constant running time--that is the amount of time it takes to determine the answer is NOT dependent of the value of N. Mar 14, 2014 at 22:42
  • 2
    Big-O notation is not about running time or memory use, but about the behavior of functions. The first sentence from the Wikipedia article you link to: "In mathematics, big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions." Algorithms come into play only when the functions you deal with happen to describe some characteristic of an algorithm, such as the number of comparisons made by a sort. In the case here it's wrong to say that f is in O(1) because f grows without bound.
    – Joni
    Mar 15, 2014 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.