What Are We Measuring?

When we talk about the efficiency of an algorithm, we're not interested in the exact time it takes to run on a specific computer (e.g., "0.02 seconds"). That time will change based on the computer's speed.

Instead, we are interested in how the algorithm's performance scales as the size of the input data grows. This is called asymptotic analysis.

1. Big O Notation (O): The Upper Bound (Worst-Case)

This is the most common and important one you'll encounter. Big O describes the worst-case scenario. It gives you an upper bound on an algorithm's performance, guaranteeing it will never be slower than a certain rate of growth.

Analogy: If a delivery service guarantees your package will arrive in "Big O of 3 days" or O(3), it means it will take at most 3 days. It might arrive in one or two, but it will never take four.

Common Big O Complexities:

O(1) - Constant Time: The algorithm takes the same amount of time regardless of the input size.

PHP

// Accessing an array element by key is always O(1)
$data = ['a', 'b', 'c'];
echo $data[1]; // Instant, no matter how big the array

O(n) - Linear Time: The performance grows in a straight line with the size of the input (n). A loop through all n items is the classic example.

PHP

// Looping through the array is O(n)
foreach ($data as $item) {
    // ... do something ...
}

O(n 2) - Quadratic Time: The performance is proportional to the square of the input size. A nested loop is the classic example. These algorithms become slow very quickly as n grows.

PHP

// A nested loop is O(n^2)
foreach ($data as $item1) {
    foreach ($data as $item2) {
        // ... do something ...
    }
}

2. Big Omega Notation (

Omega): The Lower Bound (Best-Case)

Big Omega is the opposite of Big O. It describes the best-case scenario. It gives you a lower bound, guaranteeing the algorithm will never be faster than a certain rate of growth.

Analogy: If the delivery time is Omega(1), it means it will take at least one day. It will never arrive instantly.

Example: Searching for an item in an unsorted array.

Worst-Case (O(n)): The item is the last one in the array, so you have to check all n elements.

Best-Case ( Omega(1)): The item is the very first one you check.

3. Big Theta Notation (

Theta): The Tight Bound (Average-Case) Big Theta is used when an algorithm's best-case and worst-case performance are the same. It "tightly binds" the function from above and below.

Analogy: If the delivery time is Theta(3), it means it will take exactly around 3 days, not much more and not much less.

Example: The simple foreach loop from our O(n) example is also Theta(n). You always have to touch every single element, so the best case, worst case, and average case are all the same.

Conclusion: Why Big O is King

In the professional world of programming, you will almost always hear people talk about Big O. This is because as software engineers, we are primarily concerned with the worst-case scenario. We need to know how our application will behave under maximum load, so we design and plan for the upper bound of its performance.