Search Algorithms & Complexity lab report

1. Title and aim

Empirical Analysis of Search Algorithms and Asymptotic Complexity. 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.

2. Abstract

Seven benchmark trials were generated across input sizes n = 64 to n = 4096 elements. An ordinary least-squares regression of worst-case key comparisons against logarithmic entropy log₂(n) yielded an empirical complexity multiplier of 1.0000 comparisons/bit, demonstrating exact agreement with the theoretical divide-and-conquer bound (difference = 0.0000%). The results empirically prove that Binary Search exhibits optimal Θ(log₂ n) asymptotic scaling, outperforming linear search by a factor of over 315× at n = 4096.

3. Apparatus and fixed settings

• Virtual Execution Engine & Instruction Counter: 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.
• Monotonically Ordered Contiguous Memory Array: 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.
• Low, High, and Mid Register Pointer System: 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.
• Target Key Comparator & ALU Logic Unit: 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.
• Microsecond Algorithmic Profiler & Telemetry Unit: Records wall-clock elapsed execution time, CPU cycle estimates, memory read bandwidth, and decision tree traversal depth across repeated benchmark runs.
• Synthetic Key Distribution & Randomization Generator: Generates uniform, clustered, and adversarial key distributions to evaluate algorithmic stability, average-case behavior, and degenerate worst-case edge scenarios.
• Monotonically sorted array with distinct integer keys uniformly spaced: A[i] = 2·i + 1.
• Worst-case search target key deliberately chosen outside the array bounds (target key K = 2·n + 10) to force maximal decision tree depth.
• Three-way comparison primitive (<, ==, >) executed atomically per search iteration.
• Hardware cycle counts and comparison primitives tracked via high-resolution simulated execution counters.

4. Theory and graph choice

Search algorithms constitute the cornerstone of algorithmic computer science, data structures, and information retrieval. In this computational laboratory, we bridge the gap between abstract mathematical complexity theory (Big-O, Big-Omega, Big-Theta notations) and concrete empirical execution metrics. By measuring atomic key comparisons across systematically scaled arrays, we quantitatively verify the profound divide-and-conquer efficiency of Binary Search compared to exhaustive sequential scans, demonstrating how logarithmic time complexity enables planetary-scale data lookups.

The mathematical regression fits the linear model y = mx + b, where x = log₂(n) represents input entropy in bits, y = C represents discrete key comparisons, m represents the logarithmic scaling factor, and b represents baseline termination comparison overhead. The gradient has physical units comparisons/bit.

5. Method

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.

6. Observations and calculation table

All benchmark observations use strictly controlled memory buffers. Values are recorded deterministically from the algorithmic comparator register. Residuals are computed relative to the ordinary least-squares regression line.

Download the sample observations (CSV) ↓

7. Worked calculation for one observation

8. Graph, gradient and final calculation

Circular markers represent empirical benchmark observations. The solid line represents the ordinary least-squares asymptotic linear fit.

9. Uncertainty and comparison

Percentage difference = |estimate − theoretical value| / |theoretical value| × 100 = 0.0000%.

For n = 7 benchmark observations, Σresidual² = 0.00000; s² = Σresidual²/(n − 2). Gradient standard error = √[s²/Σ(x − x̄)²] = 1.8898e-07. Intercept standard error = √[s²(1/n + x̄²/Σ(x − x̄)²)] = 1.7423e-06.

Propagating the fit parameters yields a fit standard error of 1.8898e-07 comparisons/bit, with an ideal coefficient of determination R² = 1.000000.

In deterministic comparison-based algorithm analysis, the theoretical worst-case operation count C_max(n) = ⌊log₂ n⌋ + 1 is an exact mathematical invariant. Unlike continuous physical instrumentation, there is no analog sensor noise, thermal fluctuation, or calibration drift in counting atomic discrete machine instructions. However, in physical semiconductor computers, wall-clock execution latency deviates from pure mathematical comparison counts due to hardware microarchitectural phenomena: (1) L1/L2/L3 cache line hierarchy fills and Translation Lookaside Buffer (TLB) virtual memory page walks; (2) Branch predictor mispredictions in conditional jumps (`if (A[mid] < K)`), which flush deep 14-to-20 stage microprocessor execution pipelines and incur 15 to 20 cycle stalls; (3) Hardware spatial prefetchers, which optimize sequential linear access patterns over random binary bisections for small arrays (n ≤ 64); and (4) Operating system preemptive kernel scheduling interrupts and thread context switches. Ordinary least-squares regression across systematically doubled array sizes n in [64, 4096] extracts the fundamental scaling multiplier k_search = 1.0000 comparisons/bit with zero residual variance (R² = 1.00000), verifying the asymptotic divide-and-conquer bound Θ(log₂ n) with mathematical certitude.

10. Result and discussion

The empirical benchmark observations perfectly align with the theoretical divide-and-conquer recurrence T(n) = T(n/2) + O(1). The slope m = 1.0000 confirms that exactly one additional comparison is required each time the dataset size doubles, illustrating how logarithmic algorithms tame exponential data volume growth in modern computer systems.

11. Precautions and limitations

• Verify array sortedness prior to executing binary search; executing binary search on an unsorted buffer produces unpredictable erroneous results and violates algorithmic invariants.
• Always employ the overflow-safe midpoint calculation mid = low + (high - low) / 2 to guarantee numerical stability across arbitrary 32-bit and 64-bit address spaces.
• Maintain strict loop termination conditions (low <= high) to prevent infinite loops when the search target key is strictly absent from the collection.
• When measuring empirical execution wall-clock time, warm up the CPU cache and execute multiple benchmark iterations to eliminate operating system context-switching noise and initial cold-cache loading artifacts.

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.

12. Conclusion

This laboratory investigation quantitatively demonstrated the asymptotic complexity of search algorithms. Through empirical benchmarking across arrays ranging from 64 to 4096 elements, we verified that Binary Search achieves an optimal logarithmic scaling gradient of k_search = 1.0000 comparisons/bit, matching the theoretical bound with zero residual error. The experiment highlights why divide-and-conquer is a foundational paradigm of modern computational infrastructure.