TypeScript Report — HW3 Language Comparison

Language / compiler / runtime version

TypeScript Version 7.0.2 (tsc --version) compiling to Node.js v22.18.0 (node --version), both confirmed inside WSL2 Ubuntu 26.04 "Resolute Raccoon". Compilation used tsconfig.json with "target": "ES2020" (needed for the bigint type returned by process.hrtime.bigint()), "module": "CommonJS", and "types": ["node"] (Node's ambient type declarations, installed as the sole dev dependency via npm install --save-dev @types/node). No other optimization flags — the emitted quicksort.js runs on the stock V8 engine embedded in Node 22, JIT-compiled at runtime just like plain JavaScript.

Machine: AMD Ryzen 7 5800H (8 cores / 16 threads, ~3.2 GHz base), 32 GB RAM, Windows 11 Pro host, benchmark executed inside WSL2 Ubuntu.

Random pivot / RNG

Randomized pivot selection follows CLRS RANDOMIZED-PARTITION: at every partition call on subarray arr[p..r], a pivot index is drawn uniformly at random from [p, r] via a helper randomInt(lo, hi) built on Math.random() (lo + Math.floor(Math.random() * (hi - lo + 1))). That element is swapped into position r, and a standard Lomuto partition then runs around it (elements <= pivotValue are swapped into the growing left region as the scan index j advances, and the pivot is finally swapped into its correct place at i + 1). randomizedQuicksortHelper then recurses on arr[p..q-1] and arr[q+1..r]. The same Math.random() call (Math.floor(Math.random() * 1_000_000)) is used to generate the input arrays for each iteration; data generation is not timed (only the randomizedQuicksort(arr) call is bracketed by process.hrtime.bigint()). Math.random() uses V8's xorshift128+-based PRNG, seeded internally by the engine at startup — no explicit seed was set. Array.prototype.sort was never called anywhere in the implementation.

External code used

No external code used — original implementation based on CLRS RANDOMIZED-QUICKSORT/RANDOMIZED-PARTITION pseudocode (Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 5).

Results

Built and run via:

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/typescript' && tsc && node quicksort.js"

(tsc with no filename argument, so it reads tsconfig.json; see the typescript/README.md for why tsc quicksort.ts alone fails to compile.)

Loop stopped after 15 iterations because the measured time for n=32,768,000 (4.040789s) exceeded the 4.0s cutoff (well before the 25-iteration or 200,000,000-element caps were reached). Full results (also in ../results/typescript.csv):

Total wall-clock time for the whole run (time node quicksort.js, all 15 data-generation + sort iterations plus Node startup, not counting the separate tsc compile step which took well under a second): ~8.8s (real 0m8.805s).

Growth analysis

For expected O(n log n) behavior, doubling n should multiply the running time by roughly 2 * (log2(2n) / log2(n)), which shrinks slowly from about 2.2x (near n=1,000, where log2(n)≈10) toward about 2.08x as n grows past 16 million (log2(n)≈25 at n≈32,768,000). The smallest few n values (1,000 → 2,000 → 4,000) show erratic, even sub-1x ratios (0.29x, 0.91x) purely because their absolute times are a fraction of a millisecond — right at the resolution floor of process.hrtime.bigint() combined with V8 JIT warm-up (the interpreter/baseline compiler runs the first few calls before the optimizing compiler kicks in), so timing noise dominates any real signal there. From n=8,000 onward the observed per-doubling ratios settle into the 1.70x–2.66x range, clustering close to the theoretical ~2.1x–2.2x band — e.g. 64,000→128,000 at 2.09x, 512,000→1,024,000 at 2.09x, 1,024,000→2,048,000 at 2.06x, all within a few percent of prediction — with two more visible outliers at 4,096,000→8,192,000 (2.66x) and 8,192,000→16,384,000 (1.70x), plausibly V8 garbage-collector pauses as the array size crosses generational-GC and cache-size boundaries, which then partially cancel out (a slow doubling tends to be followed by a fast one). Overall this is consistent with expected O(n log n) growth for randomized quicksort. No stack-overflow or other anomalies occurred; expected recursion depth is O(log n) (≈25 at the largest n reached here), far under Node's default call-stack limit.

Comparison with plain JavaScript (javascript/ sibling): as expected, since tsc compiles TypeScript straight down to ordinary JavaScript that then runs on the exact same Node 22 / V8 engine, the two languages are not really two different runtimes for benchmarking purposes — TypeScript's type annotations are erased entirely at compile time and have zero effect on the emitted code's runtime behavior. The JavaScript sibling run (../results/javascript.csv) shows essentially identical timings at every matching n — e.g. 1,024,000: JS 0.0856s vs TS 0.0902s; 2,048,000: JS 0.1827s vs TS 0.1861s; 4,096,000: JS 0.3697s vs TS 0.3824s; 8,192,000: JS 0.7848s vs TS 1.0188s; 16,384,000: JS 1.7361s vs TS 1.7315s — all within normal run-to-run noise for a JIT'd, garbage-collected runtime, with no systematic gap in either direction. The one visible difference is where each run happened to cross the 4.0s stopping threshold: JavaScript's n=32,768,000 iteration finished in 3.864s (just under the cutoff) and so it went on to attempt n=65,536,000 (13.36s, its final/stopping row), whereas TypeScript's n=32,768,000 iteration finished in 4.041s (just over the cutoff) and stopped one iteration earlier. That is boundary noise, not a real language-speed difference — both language's n=32,768,000 timings (3.864s vs 4.041s) are within about 4.6% of each other, and either run could easily have landed on the other side of the 4.0s line on a repeat trial. This confirms the expected result stated in the assignment protocol: TypeScript and JavaScript should perform nearly identically here because they compile down to the same JS runtime.