phpalgorithmprofilingbig-oqcachegrind

One-pass algorithm (clarification needed) Why the space complexity is O(1)?


From en.wikipedia:

A one-pass algorithm generally requires O(n) (see 'big O' notation) time and less than O(n) storage (typically O(1)), where n is the size of the input.

I made a test with xdebug.profiler_enable=1:

function onePassAlgorithm(array $inputArray): int
{
    $size = count($inputArray);
    for ($countElements = 0; $countElements < $size; ++$countElements) {
    }

    return $countElements;
}

$range = range(1, 1_000_000);
$result = onePassAlgorithm($range);

The memory usage of this code in qcachegrind is: 33 558 608 bytes, and all 100% of them was used by the range() function.
And this part seems to me ok, because inside the onePassAlgorithm function we have only two int variables.
And that's the reason why space complexity is O(1).

Then I made another test:

function onePassAlgorithm(array $inputArray, int $twoSum): array
{
    $seen_nums = [];
    foreach ($inputArray as $key => $num) {
        $complement = $twoSum - $num;
        if (isset($seen_nums[$complement])) {
            return [$seen_nums[$complement], $key];
        }
        $seen_nums[$num] = $key;
    }

    return [];
}

$range = range(1, 1_000_000);
$result = onePassAlgorithm($range, 1_999_999);

In qcachegrind we can see that onePassAlogorithm function uses only 376 bytes (the size of the return statement). Don't we need more to sequentially save in $seen_nums variable? So again space complexity is O(1)?

result of the second code in qcachegrind

My question is: Why qcachegrind shows that the variable $seen_nums in which we copy the entire $inputArray consumes no memory?

Or in other words why the storage complexity of my second realisation of this algorithm is O(1)?


Solution

  • From Xdebug documentation:

    [2007-05-17] — Removed support for Memory profiling as that didn't work properly.

    [2015-02-22] — Xdebug 2.3.0 Added the time index and memory usage for function returns in normal tracefiles.

    So the reason of my confusion was in that xdebug profiles shows only memory usage for function returns, and not the full memory profiling that i was expected.