PHP Big O Linear Time O(n)

One Pass Over the Data

O(n) means linear time: the work grows in step with the input. Twice the elements, twice the steps.

In PHP, linear time usually looks like one foreach loop over an array. Every algorithm that must at least look at every element — summing, counting, searching an unsorted array — cannot be faster than O(n).

Linear is a good complexity. Millions of elements are no problem for one pass.

Linear Search

When the array is not sorted, the only way to find a value is to check the elements one by one, from the start. That is a linear search.

In the worst case — the value is last, or not there at all — the loop visits all n elements. That worst case is what O(n) describes.

Find a value and its position

The loop checks "one", "two", "three" before it reaches "four" — 4 steps for a match at index 3. break stops the loop as soon as the value is found.

Write a PHP script that searches the array one, two, three, four, five for the word four with a plain loop, counting the steps. When found, print the index and the number of steps, then stop the loop with break.

> Output: PHP script

Prompt

Write a PHP script that searches the array one, two, three, four, five for the word four with a plain loop, counting the steps. When found, print the index and the number of steps, then stop the loop with break.

Output: PHP script

<?php

$words = ["one", "two", "three", "four", "five"];
$steps = 0;

foreach ($words as $i => $w) {
  $steps++;
  if ($w === "four") {
    echo "found at index $i after $steps steps\n";
    break;
  }
}

Visiting Every Element

Many everyday tasks are one pass over the whole array: add all values, keep the biggest one seen so far, count the elements that pass a test. Each element is touched exactly once, so all of them are O(n).

Doing two or three of these passes in a row is still linear — O(2n) and O(3n) collapse to O(n).

Sum all elements

The loop adds every element to $sum. 8 elements, 8 additions — the classic one-pass shape.

Write a PHP script that sums the array 3, 1, 4, 1, 5, 9, 2, 6 with one loop and prints how many elements it summed and the total.

> Output: PHP script

Prompt

Write a PHP script that sums the array 3, 1, 4, 1, 5, 9, 2, 6 with one loop and prints how many elements it summed and the total.

Output: PHP script

<?php

$nums = [3, 1, 4, 1, 5, 9, 2, 6];

$sum = 0;
foreach ($nums as $n) {
  $sum += $n;
}

echo "sum of ", count($nums), " elements: $sum\n";

Find the biggest value

$max starts as the first element; every element that is bigger replaces it. After one pass the biggest value, 9, remains.

Write a PHP script that finds the biggest value in the array 3, 1, 4, 1, 5, 9, 2, 6 with one pass: start with the first element as the maximum and replace it whenever a bigger one appears. Print the biggest value.

> Output: PHP script

Prompt

Write a PHP script that finds the biggest value in the array 3, 1, 4, 1, 5, 9, 2, 6 with one pass: start with the first element as the maximum and replace it whenever a bigger one appears. Print the biggest value.

Output: PHP script

<?php

$nums = [3, 1, 4, 1, 5, 9, 2, 6];

$max = $nums[0];
foreach ($nums as $n) {
  if ($n > $max) {
    $max = $n;
  }
}

echo "biggest value: $max\n";

Count the matches

The loop tests every word with strlen($w) > 3 and counts the hits. Three words are longer than 3 letters.

Write a PHP script that counts how many words in the array one, two, three, four, five are longer than 3 letters, then prints the count in a sentence.

> Output: PHP script

Prompt

Write a PHP script that counts how many words in the array one, two, three, four, five are longer than 3 letters, then prints the count in a sentence.

Output: PHP script

<?php

$words = ["one", "two", "three", "four", "five"];

$count = 0;
foreach ($words as $w) {
  if (strlen($w) > 3) {
    $count++;
  }
}

echo "$count words are longer than 3 letters\n";