Однопроходный алгоритм (требуется пояснение) Почему сложность пространства O(1)?

Question

Из en.wikipedia:

Однопроходный алгоритм обычно требует времени O(n) (см. Обозначение "big O") и меньше O(n) памяти (обычно O(1)), где n - размер входных данных.

Я провел тест с 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);

Использование памяти этим кодом в qcachegrind составляет: 33 558 608 байт, и все 100% из них были использованы функцией range ().
И эта часть мне кажется хорошей, потому что внутри функции onePassAlgorithm у нас есть только две переменные типа int.
И поэтому сложность пространства равна O(1).

Затем я сделал еще один тест:

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);

В qcachegrind мы видим, что функция onePassAlogorithm использует только 376 байт (размер оператора возврата). Разве нам не нужно что-то большее для последовательного сохранения в переменной $ visible_nums? Итак, снова сложность пространства O(1)?

Мой вопрос: почему qcachegrind показывает, что переменная $ visible_nums, в которую мы копируем весь $ inputArray, не потребляет памяти?

Или, другими словами, почему сложность хранения моей второй реализации этого алгоритма составляет O(1)?

Answer 1

Из документации Xdebug:

[2007-05-17] - Удалена поддержка профилирования памяти, так как это не работало должным образом.

[2015-02-22] - Xdebug 2.3.0 Добавлен индекс времени и использование памяти для возврата функций в обычных файлах трассировки.

Итак, причина моего замешательства заключалась в том, что профили xdebug показывают только использование памяти для возврата функций, а не полное профилирование памяти, как я ожидал.