Asymptotic Complexity Analyzer
A Java Swing app that measures the real execution time of four reference growth orders on the JVM, plots the curves live, and checks a fitted prediction against a fresh measurement — the foundational practice of the Advanced Algorithms course.
Asymptotic Complexity Analyzer
Practice 1 for the Advanced Algorithms course (21747) at the Universitat de les Illes Balears. A Java Swing desktop application, built on a Model–View–Controller architecture, that measures and plots the real execution time of several reference growth orders and contrasts them with their theoretical asymptotic behaviour. It is the foundational practice of the course: it fixes the MVC skeleton, the event-based communication protocol and the benchmarking style reused by every later practice.
The problem
The tool runs four synthetic workloads whose cost matches a known order of growth and, for a configurable series of input sizes, records how long each one actually takes on the JVM:
- O(n) — linear,
- O(n · log n) — linearithmic,
- O(n²) — quadratic,
- O(n² · log n) — quadratic-logarithmic.
Each workload runs on its own thread, times itself with System.nanoTime(), stores one (size, time) point per step and streams a progress notification back to the interface, which draws the four curves as they fill in. From the last consolidated point of a run the controller derives a proportionality constant, uses it to predict the time for a target size, and then compares that prediction against a fresh measurement — a small window onto extrapolation error, JIT warm-up and scheduling noise.
About
- MVC + message protocol — the model owns the data, the view only draws, and the controller orchestrates everything; components never talk directly but exchange text messages through the
Notifycontract, which centralizes the control flow and makes the execution traceable. - Concurrent workers — every growth order is an
AbstractProcesssubclass running in its own thread, so the four families are measured concurrently while the UI stays responsive. - Model — immutable value objects (
DataPoint,AlgorithmResult) hold the measured series; the four*Processclasses provide the computational loads. - View — a header with an
IDLE/RUNNINGbadge, a control panel to configure the experiment, a live chart and a status panel with aggregated telemetry (samples, fitted constants, expected times).
Executing the project
Requires a JDK 17 or newer — plain Java with Swing, no external dependencies or build tool. Open the P1/ folder in IntelliJ IDEA and run practice1.Main. Configure the input sizes and target in the control panel and start the run to watch the four curves grow and the prediction be checked against a real measurement.