Design & Analysis of Algorithms

AlgoBench

Advanced algorithm design, complexity analysis and large-scale benchmarking: theory vs. measured performance, across eight paradigms. Supervisor: Jayapriya D, Dept. of Computer Science.

14benchmark suites

8paradigms

4web · ipynb · Colab · Streamlit

Paradigms covered

Choosing a paradigm

The question is not which paradigm is best, but which one matches the structure of the problem.

Ask	If yes, reach for	Evidence in this project
Does it split into independent, same-shaped subproblems?	Divide & conquer	Merge sort vs bubble sort
Optimal substructure and overlapping subproblems?	Dynamic programming	Fibonacci call tree; knapsack table
Does a local choice provably extend to a global optimum?	Greedy	Dijkstra; greedy knapsack quality
Can partial solutions be rejected cheaply?	Backtracking / branch & bound	N-Queens nodes; knapsack B&B
Is the problem NP-hard and near-optimal acceptable?	Approximation	Vertex cover ratio
Could adversarial input hurt a fixed strategy?	Randomized	Random-pivot quicksort

Methodology

How the project went from a problem statement to comparable numbers.

1Model the problemState inputs, outputs and the correctness criterion.

2Derive the boundRecurrence, recursion tree or substitution gives Θ, O and Ω.

3Implement variantsNaive and optimized versions that must return identical answers.

4Generate inputsRandom inputs at doubling sizes; a fixed shape per suite.

5MeasureTime, node counts, solution quality and peak memory, best of repeated runs.

6Verify and fitCross-check outputs, then fit c·f(n) and report R² and the empirical exponent.

Benchmark protocol

Every optimized algorithm is asserted equal to a reference (sorted(), DP optimum, Bellman-Ford) before timing.
Use the best of repeated runs to reduce scheduler and garbage-collection noise.
Count nodes or operations where time is too noisy; counts are deterministic.
Change one variable at a time: algorithm, then input size.
Judge scaling by the fitted exponent and R², not by a single timing.

Scale explorercomputed live

Drag to change the input size. Time assumes 10⁹ simple operations per second.

n =

When the better algorithm actually winscomputed live

Growth rates

Why asymptotics matter: at n = 20, 2ⁿ is already past the chart while n log n barely moves.

Live benchmark labmeasured in your browser

Real code, timed in your browser (best of 3 runs). Press Run to draw the chart and tables. Memory profiling (tracemalloc) lives in the Python notebook and Streamlit app, since browsers cannot measure per-algorithm heap reliably. Compare the measured curve against the theoretical bound.

log y-axis theory overlay (fit c·f(n))

Slowdown vs the best algorithmderived from the run above

Each cell is how many times slower that algorithm is than the fastest one at the same input size. Deeper rose = further from best.

Measurement statisticsmeasured in your browser

One algorithm, run 60 times. Why the protocol discards warm-up runs and reports percentiles instead of the average alone.

Warm-up: time per run

Latency distribution (quantiles of the 60 runs)

Mean vs percentiles

Amortized analysis: cost of each append, doubling policycomputed live

Spikes at appends 2, 3, 5, 9 and 17 are resizes that copy the whole array; the running average stays below 3, which is the O(1) amortized bound.

Paradigm profilesample scores 1–5

Qualitative scores from the project's analysis: dynamic programming buys optimality with memory; greedy is fast and light but not always optimal; backtracking is exact but slow.

Playground: bring your ownruns in your browser

1. Benchmark your own array

Paste numbers separated by commas, spaces or new lines (up to 20,000).

2. Estimate the complexity of your own code

Define a function named f. It receives an array of n integers or the integer n, and must not modify the input array. Your code runs only in your browser, and the page cannot stop an infinite loop, so keep the sizes modest.

sizes

3. Race your own sorting code against built-ins

Paste a function named f that sorts. It receives a copy of your array from §1 and must return the sorted array (or sort in place). It is checked against Array.sort for correctness, then timed head-to-head with Bubble, Merge, Quick and the built-in sort on the same input. Runs only in your browser.

uses the array from §1

Live arenaruns in your browser

Race three sorting algorithms on the same input, live. Pick the size and the shape of the input, then start the race.

n 80

More datameasured in your browser

Comparisons counted, not timed

Counts are deterministic, so they show the algorithm's true growth without machine noise.

Randomized quicksort: distribution over 1000 runs

Same input, random pivots. The spread of comparison counts shows why randomization protects against bad cases.

Results datasetmeasured in Python

162 data points across 14 suites, generated by algobench.py (Python 3.12.3, one fixed reference run, also saved as results.csv). Browser timings above vary by device; this dataset is the stable reference.

log y-axis

Fitted growth per algorithm

Recurrences & bounds

Algorithm	Recurrence	Method	Bound
Merge sort	T(n)=2T(n/2)+n	Master (case 2)	Θ(n log n)
Binary search	T(n)=T(n/2)+1	Master (case 2)	Θ(log n)
Naive Fibonacci	T(n)=T(n-1)+T(n-2)+1	Recursion tree	Θ(φⁿ) ⊂ O(2ⁿ)
Strassen	T(n)=7T(n/2)+n²	Master (case 1)	Θ(n^2.81)
Dynamic array append	—	Amortized (aggregate)	O(1) amortized

Algorithms in motion

Step-by-step visualisations: watch the work each paradigm actually does.

delay

Knapsack DP table (orange outline = items chosen on traceback; shading = value)

Dijkstra: shortest-path tree grows greedily

Dynamic programming: why naive Fibonacci explodes

LCS: dynamic programming on two strings

Backtracking: N-Queens search with pruning

delay teal = safe placement tried, rose = conflict (prune), then backtrack

Graph search: BFS wave on a maze

Master theorem solver

T(n) = T(n/) + Θ(n^)

Try (2,2,1) merge sort · (1,2,0) binary search · (8,2,2) naive matrix multiply · (7,2,2) Strassen.

Where the work happens in the recursion treecomputed live

Work per level for n = 1024, updating with the solver above. Teal = root, rose = leaves. Growing bars: leaves dominate (Case 1). Flat bars: balanced work (Case 2). Shrinking bars: root dominates (Case 3).

Complexity cheat sheetreference

Algorithm	Paradigm	Time	Space
Merge sort	Divide & conquer	Θ(n log n)	O(n)
Randomized quicksort	Randomized	O(n log n) expected	O(log n)
0/1 Knapsack	Dynamic programming	O(nW) (pseudo-poly)	O(W)
Kruskal MST	Greedy	O(E log E)	O(V)
Dijkstra (heap)	Greedy	O((V+E) log V)	O(V)
Bellman-Ford	Dynamic programming	O(VE)	O(V)
BFS / DFS / topological sort	Graph	O(V+E)	O(V)
Edmonds-Karp max-flow	Network flow	O(VE²)	O(V+E)
N-Queens	Backtracking	exponential, heavily pruned	O(n)
TSP / 0-1 ILP	Branch & bound	O(n!) worst case	O(n)
Vertex cover 2-approx	Approximation	O(V+E)	O(V)

Complexity classes

Polynomial-time reduction map (A → B: B is at least as hard as A):

SAT→3-SAT→Clique→Vertex Cover→Hamiltonian Cycle→TSP

3-SAT→Subset Sum→Partition→0/1 Knapsack (pseudo-polynomial DP exists because W is numeric, not a size bound)

PSolvable in polynomial time: MST, shortest paths, max-flow.

NP / NP-completeVerifiable in polynomial time: SAT, Subset Sum, TSP (decision). Polynomial reductions link them.

NP-hardAt least as hard as NP-complete: tackled with exact search (B&B), approximation (2-approx vertex cover) and heuristics.

Test environment & limits

Detected from the device viewing this page, so the numbers above can be interpreted honestly.

The numbers CAN sayRelative scaling shape, crossover points, the effect of pruning and memoization (node counts are deterministic), and whether each variant returns identical answers.

The numbers CANNOT sayAbsolute production speeds (one machine, JavaScript and Python, timer noise), cache and branch-prediction effects, adversarial worst cases, parallel or distributed behaviour, or behaviour beyond the tested sizes.

Run it yourself

Interactive Streamlit appRun benchmarks in Python with memory profiling.

Jupyter / ColabAlgoBench.ipynb: self-contained notebook.

GitHub repoSite, notebook, app and dataset in one place.

This siteStatic single file, hosted on GitHub Pages.

pip install -r requirements.txt
jupyter notebook AlgoBench.ipynb      # or open in Colab
streamlit run streamlit_app.py        # interactive benchmark app
open index.html                       # this site, works offline

Contact

Questions, feedback or collaborationEmail harshinisuresha7@gmail.com