Complexity Analysis and Code Optimization with PHP

Complexity Analysis and Code Optimization with PHP | CodeSignal Learn

Introduction

Welcome to the lesson! Today, our journey will take us through the captivating world of Complexity Analysis and techniques for optimization. These fundamental concepts are crucial for every programmer, especially those seeking to build efficient and scalable programs. Having a firm understanding of how code impacts system resources enables us to optimize it for better performance. Isn't it fascinating how we can tailor our code to be more efficient? So, buckle up and let's get started!

Remind Complexity Analysis

O(n)

Basic Examples of Optimization

O(n)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

First things first, let's remind ourselves of what Complexity Analysis is. Simply put, Complexity Analysis is a way of determining how our data input size affects the performance of our program, most commonly in terms of time and space. In more technical terms, it’s a theoretical measure of the execution of an algorithm, particularly the time or memory needed, given the problem size n, which is usually the number of items. Interested in how it works?

Let's take, for example, a linear search function that looks for a value $x in an array of size n. In the worst-case scenario, the function has to traverse the entire array, thus taking time proportional to n. We would say that this function has a time complexity of $O(n)$ .

PHP

<?php
function linearSearch($x, $array) {
    foreach ($array as $index => $value) {
        if ($value === $x) {
            return $index;
        }
    }
    return -1;
}

$array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
$index = linearSearch(5, $array);
// index becomes 4
echo "Index: " . $index;
?>

Now that we have refreshed our understanding of complexity analysis, let's delve into some basic examples of optimization. Optimization involves tweaking your code to make it more efficient by improving its runtime or reducing the space it uses.

An easy example of optimization could be replacing iterative statements (like a for loop) with built-in functions or using simple mathematical formulas whenever possible. Consider two functions, each returning the sum of numbers from 1 to an input number n.

The first one uses a for loop:

PHP

<?php
function sumNumbers($n) {
    $total = 0;
    for ($i = 1; $i <= $n; $i++) {
        $total += $i;
    }
    return $total;
}

$result = sumNumbers(1000000);
echo "Sum: " . $result;
?>

This function has a time complexity of $O(n)$ , as it iterates over numbers from 1 to n summing them up.

The second one uses a simple mathematical formula:

PHP

<?php
function sumNumbers($n) {
    return ($n * ($n + 1)) / 2;
}

$result = sumNumbers(1000000);
echo "Sum: " . $result;
?>

The second function has a time complexity of $O(1)$ because it calculates the sum in constant time with a single formula, independent of the input size n.

While both functions yield the same result, the second one is much more efficient. It doesn't need to iterate through all the numbers between 1 and n. This is a classic example of optimization, where we've reimagined our approach to solving a problem in a way that uses fewer resources.

Note that although all the values between 1 and n are of type int, we must consider that the result of the operations can exceed the limits of PHP's int type on some systems. Thus, PHP implicitly handles large integers, but it's good to be aware of potential overflows in other languages.

Deeper Dive into Optimization

O(n^2)

Next, let's explore a more complex optimization example with a function that checks for duplicate numbers in an array. Here's the initial version of such a function, which uses two for loops:

PHP

<?php
function containsDuplicate($array) {
    for ($i = 0; $i < count($array); $i++) {
        for ($j = $i + 1; $j < count($array); $j++) {
            if ($array[$i] === $array[$j]) {
                return true;
            }
        }
    }
    return false;
}

$array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1];
$result = containsDuplicate($array);
echo "Contains Duplicate: " . ($result ? "Yes" : "No");
?>

<?php
function containsDuplicate($array) {
    for ($i = 0; $i < count($array); $i++) {
        for ($j = $i + 1; $j < count($array); $j++) {
            if ($array[$i] === $array[$j]) {
                return true;
            }
        }
    }
    return false;
}

$array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1];
$result = containsDuplicate($array);
echo "Contains Duplicate: " . ($result ? "Yes" : "No");
?>

This function checks every pair of numbers, resulting in a time complexity of $O(n^2)$ . Here's why: For every element in the array, it compares it with almost every other element. So, the number of operations grows quadratically with $n$ , hence the complexity $O(n^2)$ .

However, we can optimize this function by sorting the array first and then checking the elements next to each other:

PHP

<?php
function containsDuplicate($array) {
    sort($array);
    for ($i = 1; $i < count($array); $i++) {
        if ($array[$i] === $array[$i - 1]) {
            return true;
        }
    }
    return false;
}

$array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1];
$result = containsDuplicate($array);
echo "Contains Duplicate: " . ($result ? "Yes" : "No");
?>

<?php
function containsDuplicate($array) {
    sort($array);
    for ($i = 1; $i < count($array); $i++) {
        if ($array[$i] === $array[$i - 1]) {
            return true;
        }
    }
    return false;
}

$array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1];
$result = containsDuplicate($array);
echo "Contains Duplicate: " . ($result ? "Yes" : "No");
?>