Measure the empirical operation counts (key comparisons) of Linear Search and Binary Search across ordered datasets of varying size n from 64 to 4096 elements, verify the asymptotic complexity bounds Θ(n) and Θ(log₂ n), and extract the fundamental logarithmic scaling multiplier k_search using ordinary least-squares linear regression. Explore interactive search algorithms, compare operation counts and analyse complexity scaling.
Ready to execute array size benchmark.
Adjust array size n, then execute benchmark.
Operation counts are generated deterministically by the exact algorithmic execution model. Modern hardware benchmarks additionally reflect cache line prefetching and branch misprediction penalties.
The simulated execution model evaluates idealized algorithmic operation counts (atomic comparisons and index updates). In real physical computer hardware, wall-clock execution time is heavily modulated by non-algorithmic architectural factors including L1/L2/L3 CPU cache hierarchy line fills, TLB (Translation Lookaside Buffer) paging misses, hardware prefetching heuristics, speculative execution branch misprediction recovery penalties, compiler register allocation, and operating system thread scheduling latencies. Consequently, algorithmic comparison counts provide pure asymptotic scaling metrics, while hardware execution benchmarks quantify end-to-end wall-clock latency. The theoretical worst-case comparison bound for Binary Search on a sorted array of size n is exactly C_max(n) = ⌊log₂ n⌋ + 1. Under ordinary least-squares regression against x = log₂(n), the theoretical slope is exactly k_search = 1.0000 comparisons per bit of key entropy, with an intercept of b = 1.0000 comparison. For Linear Search, the worst-case comparison count is exactly C_max(n) = n, while the average successful search requires C_avg(n) = (n + 1) / 2 comparisons, exhibiting linear scaling Θ(n). Real-world wall-clock execution time additionally reflects processor cache-line prefetching, memory bus bandwidth, and branch misprediction penalties.
Simulates a deterministic Von Neumann processor architecture with dedicated hardware instruction counters, tracking atomic comparison operations, memory loads, and branch jumps without nondeterministic operating system scheduling jitter.
Allocates a contiguous block of primary random-access memory storing n distinct 32-bit integer keys arranged in strictly ascending monotonic order (A[0] < A[1] < ... < A[n-1]), providing O(1) indexed random access.
Maintains hardware register pointers delimiting the active search interval [low, high] and computes the bisecting midpoint index mid = low + ⌊(high - low) / 2⌋, preventing 32-bit signed integer arithmetic overflow.
Performs ternary key comparison between the target key K and the midpoint element A[mid], asserting equal, less-than, or greater-than status flags to direct control flow branching.
Records wall-clock elapsed execution time, CPU cycle estimates, memory read bandwidth, and decision tree traversal depth across repeated benchmark runs.
Generates uniform, clustered, and adversarial key distributions to evaluate algorithmic stability, average-case behavior, and degenerate worst-case edge scenarios.
Measure the empirical operation counts (key comparisons) of Linear Search and Binary Search across ordered datasets of varying size n from 64 to 4096 elements, verify the asymptotic complexity bounds Θ(n) and Θ(log₂ n), and extract the fundamental logarithmic scaling multiplier k_search using ordinary least-squares linear regression. Suggested independent settings: 64, 128, 256, 512, 1024, 2048, 4096 elements.
Initialize the contiguous memory array with n distinct sorted integer keys according to the selected benchmark size n in [64, 128, 256, 512, 1024, 2048, 4096]. Verify monotonic ordering across all indices such that A[i] < A[i+1] for all 0 <= i < n - 1.
Configure the search target key K. For worst-case empirical validation, select a key strictly greater than the maximum element (K = A[n-1] + 10) or choose an absent key that forces the search interval to contract until empty. Initialize the hardware register pointers low = 0 and high = n - 1.
In each search iteration, verify the loop invariance condition low <= high. Compute the midpoint index using the overflow-safe formula mid = low + Math.floor((high - low) / 2). Highlight the active search candidate subarray [low, high] on the visual workbench.
Fetch the element A[mid] from primary memory into the ALU comparison register. Execute the comparison primitive against target key K and increment the atomic comparison counter C by 1. Evaluate whether A[mid] == K, A[mid] < K, or A[mid] > K.
If A[mid] == K, terminate with successful match at index mid. If A[mid] < K, discard the lower half of the array by setting low = mid + 1. If A[mid] > K, discard the upper half by setting high = mid - 1. Render discarded elements as inactive on the visual array canvas.
Repeat iterations until low > high or the key is located. Record the final worst-case comparison count C_max into the observation notebook. Repeat the procedure across all sample array sizes n in [64, 128, 256, 512, 1024, 2048, 4096]. Compute x = log₂(n) and perform ordinary least-squares regression to extract the slope k_search.
Points are your recorded benchmark observations. The regression line validates Search Algorithms & Complexity complexity scaling.
| # | Array size n (elements) (elements) | Worst-case key comparisons C_max (comparisons) | Logarithmic key entropy log₂(n) (bits) | Key comparisons C (operations) | Remove |
|---|
No readings yet. Execute a array size benchmark and record it.