CODEWITHSUNDEEP
phpperformanceoptimizationbig-o
Lizard
Lizard

Reputation: 45032

Big O of two functions

I have been programming in PHP for a long time now, and as I don't come from a computer science / math background I only have a basic understanding of the Big O notation, so I have taken a function and tried to improve it and express them both in Big O:

Example 1

function foo($j) {
    $ids = array();
    while (count($ids) < $j) {
        $id = gen_id();  // assume this function will return you an integer
        if (!in_array($id, $ids)) {
            $ids[] = $id;
        }
    }
    return $ids;
}

I would improve this function by removing the while loop for count($ids) and replace with forloop So that count($ids) doesn't have to be evaluated every time in the loop, and also replace is_array with isset and move the values to keys (isset is quicker than in_array)

Example 2 - Improved

function foo($j) {
    $ids = array();
    for($i = 1; $i<= $j; ++$j) {
        $id = gen_id();  // assume this function will return you an integer
        if (!isset($ids[$id])) {
            $ids[$id] = true;
        }
        else {
            --$i;
        }
    }
    return $ids;
}

I would express the above functions with the following Big O Notation:

Example 1: O(n^2), Example 2: O(n)

Am I correct with my notations? Is there a better way still to do the same function?

Thanks in advance!

Upvotes: 1

Views: 624

Answers (4)

P M
P M

Reputation: 11

for ($i=0;$i<$j; ) {
  $id = gen_id();
  if (!isset($ids[$id])) {
    $ids[$id]=true;
    $i++;
  }
}

Upvotes: 1

Md Kamruzzaman Sarker
Md Kamruzzaman Sarker

Reputation: 2407

Your thinking is good but you are not correct.

The following will clarify you....

function foo($j) 
{
 for($i=1;$i<j;$i++)
 {
  // some code here
 }
 for($i=1;$i<j;$i++)
 {
 // some code here
 }
}

You may think this will be 0(2n) but The constant term does not expressed on 0 notation. So It has complexity 0(n).

Look the following

 function foo($j) 
{
 for($i=1;$i<j;$i++)
 {
    for($k=1;$k<i;$k++)
    {
     // some code here
    }
 }

}

It has the complexity 0(n^2).

Upvotes: 1

nickb
nickb

Reputation: 59709

Here is how I would write that function in a more straightforward approach: The inner for loop is the perfect scenario for a do ... while loop.

function foo( $j)
{
    $ids = array();
    for( $i = 0; $i < $j; $i++)
    {
        do
        {
            $id = gen_id();
        } while( isset( $ids[$id]));
        $ids[$id] = true;
    }
    return $ids;
}

Edit: Actually, this function is O($j) / O(n), since gen_id() and isset() are both constant O(1) (isset() is a hash table lookup). So, the inner efficiency of the for loop is constant time O(1), making the whole function O(n).

Upvotes: 1

starrify
starrify

Reputation: 14781

First of all: constant coefficients don't matter in Big O notation, which means O(n) = O(cn) for any constant c != 0.

For the 1st one, I know count($ids) takes O(1) time to evaluate, but how about in_array($id, $ids)? I don't know exactly. But if it's O(n) or O(logn), then the whole would be O(n^2) or O(nlogn). I don't think this could be implemented in O(1) time, which could give an O(n) time for the whole function.

For the 2nd one, this is O(n) and seemingly faster than the 1st one.

EDIT: I just think wikipedia has described the big O notation somehow clearly. Go and read some.

Upvotes: 1

Related Questions