<?php

function T($arr, $p) {
    foreach ($arr as $a) {
        if ($a['parent'] === $p) {
            T($arr, $a['uid']);
        }
    }
}

function testOne($numItems) {
    $arr = [];
    for ($i = 0; $i < $numItems; $i++) {
        $arr[] = [
            'uid' => $i+1,
            'parent' => rand(0, $i)
        ];
    }

    $before = hrtime()[1];
    T($arr, 0);
    $after = hrtime()[1];

    $delta = $after - $before;

    return $delta;
}

function testAvg($numItems, $numRuns) {
    $execTimes = [];
    for ($i = 0; $i < $numRuns; $i++) {
        $execTimes[] = testOne($numItems);
    }

    sort($execTimes);
    $med = round($execTimes[count($execTimes)/2] / 4206040);

    #echo("$numItems took on average $med time units. ($numRuns sample size)\n");
    echo("($numItems, $med)\n");
}

for ($i = 0; $i <= 5000; $i += 100) {
    testAvg($i, 10);
}