Comprehensive Study Guide: Linear Search, Binary Search, and Big O Complexity Analysis

Foundational Data Structures: Arrays and Strings

• Array Fundamentals and Definition:

  • Arrays serve as a primary, foundational data structure across computer science, designed to store ordered collections of elements.
  • Arrays can store heterogeneous types of data, including nested structures such as other arrays.
  • Elements are arranged linearly, where each item occupies a specific position defined by a numerical index.
  • Example array $X$ containing $9$ numerical elements:
  • Element values: [55, 66, 44, 32, 34, 56, 76, 89, 21]
  • Corresponding indices: [0, 1, 2, 3, 4, 5, 6, 7, 8]

• Memory Architecture and Address Calculation:

  • Array elements are allocated contiguously (side by side) in system memory.
  • The index acts as an offset counter representing the number of element positions from the start of the memory block, which explains why arrays are zero-indexed ($\text{index} = 0$ for the first element).
  • Given a starting base memory address and a fixed data type size, any element can be accessed in a single direct mathematical operation.
  • Calculation formula for memory location:
  • $\text{Address}(X[i]) = \text{Base Address} + (\text{Element Size in Bytes} \times i)$
  • Illustrative scenario where array $X$ starts at base address $1000$ and each integer occupies $4\,\text{bytes}$:
  • Index $0$ ($X[0] = 55$): Memory address $1000 + 4 \times 0 = 1000$
  • Index $1$ ($X[1] = 66$): Memory address $1000 + 4 \times 1 = 1004$
  • Index $2$ ($X[2] = 44$): Memory address $1000 + 4 \times 2 = 1008$
  • Index $3$ ($X[3] = 32$): Memory address $1000 + 4 \times 3 = 1012$
  • Index $4$ ($X[4] = 34$): Memory address $1000 + 4 \times 4 = 1016$
  • Index $5$ ($X[5] = 56$): Memory address $1000 + 4 \times 5 = 1020$
  • Index $6$ ($X[6] = 76$): Memory address $1000 + 4 \times 6 = 1024$
  • Index $7$ ($X[7] = 89$): Memory address $1000 + 4 \times 7 = 1028$
  • Index $8$ ($X[8] = 21$): Memory address $1000 + 4 \times 8 = 1032$
  • Because calculating the address requires only a single addition and multiplication step, array lookup by index executes in constant time ($O(1)$) regardless of total array size.

• Basic Primitive Data Types in Arrays:

  • Integer: Stores whole numbers (e.g., $42$, $-7$).
  • Real (float): Stores numbers containing fractional or decimal components (e.g., $3.14$, $-0.5$).
  • Boolean: Stores binary truth values (True, False).
  • Character: Stores a single typographical symbol, letter, or digit (e.g., 'a', '7').
  • String: Stores arbitrary contiguous sequences of textual characters, such as words, phrases, or location names (e.g., 'hello').

• String Properties and Length Notation:

  • Strings operate identically to arrays of characters, meaning each character holds a distinct position accessed via a zero-based index.
  • For the string $a = \text{'hello'}$, the character index mapping is:
  • Index $0$: 'h'
  • Index $1$: 'e'
  • Index $2$: 'l'
  • Index $3$: 'l'
  • Index $4$: 'o'
  • String length is formally denoted with vertical bars as $|a|$.
  • For $a = \text{'hello'}$, the length is $|a| = 5$.

• Worked Example: Indexing and Length Operations:

  • Let $A$ be the array [1, 1, 2, 3, 5, 8, 13, 21] with indices spanning $0$ to $7$.
  • Solving expression $P = A[0] \times A[5]$:
  • $A[0] = 1$
  • $A[5] = 8$
  • $P = 1 \times 8 = 8$
  • Solving expression $Q = |A|$:
  • Total number of elements in $A$ is $8$, so $Q = 8$.
  • Solving expression $R = A[Q - 2] + A[Q - 1]$:
  • $Q - 2 = 8 - 2 = 6$
  • $Q - 1 = 8 - 1 = 7$
  • $A[6] = 13$
  • $A[7] = 21$
  • $R = A[6] + A[7] = 13 + 21 = 34$

Linear Search Algorithm

• Principles of Linear Search:

  • Linear search represents the most straightforward sequential search strategy.
  • It is strictly required when inspecting unordered or unsorted datasets where no sorting assumptions can be made.
  • The algorithm traverses elements sequentially from left to right, comparing each encountered value against a specified target value $T$.
  • Traversal terminates immediately once the target $T$ is matched; if the end of the array is reached without matching, the algorithm concludes that $T$ is absent.
  • In the worst case, every single element must be evaluated, making execution duration directly proportional to the dataset length ($O(n)$).

• Formal Pseudocode:

  • Structured pseudocode implementation (linear_search.pseudo): text 1 X = [55, 66, 44, 32, 34, 56, 76, 89, 21] 2 T = 34 3 FOR I = 0 TO LEN(X) - 1 4 IF X[I] = T THEN 5 RETURN I 6 ENDIF 7 NEXT I 8 RETURN -1 9 END     
  • Line 4 compares array element $X[I]$ with target $T$.
  • Line 5 exits immediately upon discovery, returning index $I$.
  • Line 8 executes only after the entire loop concludes without finding $T$, returning $-1$ to denote absence.

• Step-by-Step Traversal Trace ($T = 34$):

  • Target search on array $X = [55, 66, 44, 32, 34, 56, 76, 89, 21]$ for $T = 34$:
  • Step 1 ($I = 0$): $X[0] = 55$. Evaluation: $55 \neq 34$. Continue loop.
  • Step 2 ($I = 1$): $X[1] = 66$. Evaluation: $66 \neq 34$. Continue loop.
  • Step 3 ($I = 2$): $X[2] = 44$. Evaluation: $44 \neq 34$. Continue loop.
  • Step 4 ($I = 3$): $X[3] = 32$. Evaluation: $32 \neq 34$. Continue loop.
  • Step 5 ($I = 4$): $X[4] = 34$. Evaluation: $34 = 34$. Match confirmed; return index $4$.

• Linear Search Trace Table ($T = 89$):

  • Tracing array $X$ for $T = 89$:
  • Step 1: Index $I = 0$, $X[I] = 55$, Match: No
  • Step 2: Index $I = 1$, $X[I] = 66$, Match: No
  • Step 3: Index $I = 2$, $X[I] = 44$, Match: No
  • Step 4: Index $I = 3$, $X[I] = 32$, Match: No
  • Step 5: Index $I = 4$, $X[I] = 34$, Match: No
  • Step 6: Index $I = 5$, $X[I] = 56$, Match: No
  • Step 7: Index $I = 6$, $X[I] = 76$, Match: No
  • Step 8: Index $I = 7$, $X[I] = 89$, Match: Yes, RETURN 7

• Python Implementation:

  • Script implementation (linear_search.py): ```python numbers = [4, 5, 6, 7, 3, 2, 10, 12, 13, 20]

  def linear_search(array, target): for i in range(len(array)): if array[i] == target: return i # Algorithm stops here: target found at index i return -1 # Algorithm returns -1 if target element is not found

  print(linear_search(numbers, 2)) # Returns 5 (2 is located at index 5) print(linear_search(numbers, -2)) # Returns -1 (element absent)     ```

• Comparison Metrics Across Cases:

  • Best Case: Target is located at the first position ($T = 55$ at $X[0]$). Requires exactly $1$ comparison.
  • Worst Case (Target Present at End): Target is at the final position ($T = 21$ at $X[8]$). Requires $9$ comparisons ($n$ comparisons).
  • Worst Case (Target Absent): Target is not in the array ($T = 50$). Requires checking all $9$ elements ($n$ comparisons) before exiting and returning $-1$.
  • Average Case: On average, approximately half the elements in the collection are inspected ($\approx \frac{n}{2}$ comparisons), scaling linearly as $O(n)$.

Binary Search Algorithm

• Divide-and-Conquer Methodology:
  • Binary search requires the dataset to be sorted beforehand (numerical or alphabetical order).
  • The algorithm uses a divide-and-conquer paradigm: on every cycle, it evaluates the midpoint value of the current search field and halves the remaining candidate elements.
  • If data is sorted in ascending order, comparisons check whether the target is smaller or larger than the midpoint; for descending order, these comparisons are inverted.
  • Physical Metaphor: Flipping open a physical dictionary at the midpoint, checking whether the target word alphabetically precedes or follows the current page, discarding the irrelevant half of the pages, and repeating until located.

• Algorithm Flowchart Logic:

  • 1. Start: Receive sorted array $X$ and target $T$.
  • 2. Search Field Check: Is the search field empty ($\text{start} \ge \text{end}$)?
  • If Yes: Output $-1$ and stop.
  • If No: Compute middle index: $\text{mid} = (\text{start} + \text{end}) \text{ DIV } 2$.
  • 3. Target Check: Does $X[\text{mid}] = T$?
  • If Yes: Output $\text{mid}$ and stop.
  • If No: Evaluate whether $X[\text{mid}] < T$.
    • If Yes: Discard $X[\text{mid}]$ and the entire left half; update $\text{start} = \text{mid} + 1$.
    • If No: Discard $X[\text{mid}]$ and the entire right half; update $\text{end} = \text{mid}$.
  • 4. Repeat process with updated boundaries.

• Binary Search Pseudocode:

  • Structured pseudocode implementation (binary_search.pseudo): text 1 X = [21, 32, 34, 44, 55, 56, 66, 76, 89] 2 T = 34 3 start = 0 4 end = LEN(X) 5 WHILE start < end 6 mid = (start + end) DIV 2 7 IF X[mid] = T THEN 8 RETURN mid 9 ELSEIF X[mid] < T THEN 10 start = mid + 1 11 ELSE 12 end = mid 13 ENDIF 14 ENDWHILE 15 RETURN -1 &nbsp;&nbsp;&nbsp;&nbsp;
  • The active search field extends from index $\text{start}$ to $\text{end} - 1$.

• Step-by-Step Traversal Trace ($T = 34$):

  • Target search on sorted array $X = [21, 32, 34, 44, 55, 56, 66, 76, 89]$:
  • Step 1:
    • $\text{start} = 0$, $\text{end} = 9$
    • $\text{mid} = (0 + 9) \text{ DIV } 2 = 4$
    • Check value: $X[4] = 55$
    • Comparison: $55 > 34$. Because $X[\text{mid}] > T$, discard $X[4]$ and the right half.
    • Boundary update: $\text{end} = \text{mid} = 4$
  • Step 2:
    • $\text{start} = 0$, $\text{end} = 4$
    • $\text{mid} = (0 + 4) \text{ DIV } 2 = 2$
    • Check value: $X[2] = 34$
    • Comparison: $34 = 34$. Target matches midpoint value; RETURN 2.

• Trace Table for Target ($T = 13$):

  • Binary search trace on sorted array $A = [1, 1, 2, 3, 5, 8, 13, 21]$ for target $T = 13$:
  • Step 1: $\text{start} = 0$, $\text{end} = 8$, $\text{mid} = (0 + 8) \text{ DIV } 2 = 4$, $A[4] = 5$. Action: $5 < 13$, update $\text{start} = \text{mid} + 1 = 5$.
  • Step 2: $\text{start} = 5$, $\text{end} = 8$, $\text{mid} = (5 + 8) \text{ DIV } 2 = 6$, $A[6] = 13$. Action: $13 = 13$, RETURN 6.

• Python Implementation:

  • Script implementation (binary_search.py): ```python def binary_search(arr, t): start = 0 # Starts equal to 0 (updated in loop) end = len(arr) # Set equal to size of input

    while start < end: # Stopping condition when search field is empty mid_point = (start + end) // 2 # Define middle index

    # If target is at midpoint, return index immediately
    if arr[mid_point] == t:
        return mid_point
    
    # If midpoint < target, shift lower bound past midpoint
    if arr[mid_point] < t:
        start = mid_point + 1
    # If midpoint > target, shift upper bound to midpoint
    elif arr[mid_point] > t:
        end = mid_point
    

    return -1 # Target not found     ```

• Failure Demonstration on Unsorted Data:

  • Executing binary search on unsorted data produces erroneous results because the algorithm discards elements based on false ordering assumptions.
  • Demonstration searching for target $T = 21$ in unsorted array $X = [55, 66, 44, 32, 34, 56, 76, 89, 21]$:
  • Step 1: $\text{start} = 0$, $\text{end} = 9$, $\text{mid} = 4$, $X[4] = 34$. Because $34 > 21$, algorithm assumes $21$ must reside in the left half and discards the right half (indices $4$ through $8$). The target $21$ is at index $8$ and is improperly discarded.
  • Step 2: $\text{start} = 0$, $\text{end} = 4$, $\text{mid} = 2$, $X[2] = 44$. Comparison: $44 > 21$, discard right half; $\text{end} = 2$.
  • Step 3: $\text{start} = 0$, $\text{end} = 2$, $\text{mid} = 1$, $X[1] = 66$. Comparison: $66 > 21$, discard right half; $\text{end} = 1$.
  • Step 4: $\text{start} = 0$, $\text{end} = 1$, $\text{mid} = 0$, $X[0] = 55$. Comparison: $55 > 21$, discard right half; $\text{end} = 0$.
  • Step 5: $\text{start} = 0$, $\text{end} = 0$. Search field is completely empty. Algorithm returns $-1$, incorrectly stating that $21$ is absent when it was present all along.

• Binary Decision Tree Structure:

  • A binary search across a sorted collection can be visualized as a balanced binary decision tree.
  • For $9$ items ([21, 32, 34, 44, 55, 56, 66, 76, 89]):
  • Level 1 (Comparison 1): Root at index $4$ (value $55$).
  • Level 2 (Comparison 2): Left child at index $2$ (value $34$); Right child at index $7$ (value $76$).
  • Level 3 (Comparison 3): Children at index $1$ (value $32$), index $3$ (value $44$), index $6$ (value $66$), index $8$ (value $89$).
  • Level 4 (Comparison 4): Leaves at index $0$ (value $21$) and index $5$ (value $56$).
  • With $4$ vertical levels, a maximum of $4$ comparisons is required to evaluate any of the $9$ values.

• Mathematical Derivation of Comparison Bounds:

  • Each successive comparison divides the remaining active items by $2$.
  • Starting with $n$ items, the number of elements remaining after $k$ successive halvings is:
  • $\frac{n}{2^k}$
  • In the worst case, halving continues until exactly $1$ element remains:
  • $\frac{n}{2^k} = 1 \implies n = 2^k \implies k = \log_2(n)$
  • Number of worst-case comparisons as dataset grows:
  • $n = 16\,\text{items} \implies 5\,\text{comparisons}$
  • $n = 32\,\text{items} \implies 6\,\text{comparisons}$
  • $n = 1,000\,\text{items} \implies 10\,\text{comparisons}$
  • $n = 1,000,000\,\text{items} \implies 20\,\text{comparisons}$
  • Doubling the input dataset size adds only $1$ additional comparison step ($O(\log(n))$ logarithmic complexity).

• Real-World Case Study: CCTV Investigation of Bike Theft:

  • The Scenario: Police in Cambridge established an investigative policy refusing to review security CCTV footage if the potential theft window exceeded $4\,\text{hours}$.
  • Computer Science Counterargument: A computer scientist demonstrated that applying binary search would resolve the theft within approximately one hour even if surveillance footage spanned backwards to the dawn of humanity (IFLScience, 2023).
  • Application: An investigator views the exact midpoint frame of the recording. If the bicycle is still present in the rack, the theft occurred after that timestamp; if the bicycle is gone, the theft occurred prior to that timestamp. Each check halves the remaining video duration.
  • Mathematical Modeling: In 2025, a mathematician confirmed that no more than $7$ checks are necessary to reduce an $8\,\text{hour}$ continuous surveillance tape down to a precise $5\,\text{minute}$ window, taking around $2\,\text{minutes}$ total at $15\,\text{seconds}$ per review check (Kehoe, 2025).
  • Cosmic Timescale Calculation:
  • Assuming a continuous video recording spanning the entire age of the universe, estimated at $13.8\,\text{billion years}$ (European Space Agency, 2013).
  • Converting $13.8\,\text{billion years}$ into seconds yields approximately $4.4 \times 10^{17}\,\text{seconds}$.
  • Number of halving operations needed to isolate the exact second of the theft: exactly $59\,\text{checks}$ ($2^{59} > 4.4 \times 10^{17}$).
  • To narrow the event down to an exact single video frame (at $30\,\text{frames per second}$): exactly $64\,\text{checks}$.

Comparative Search Analysis

• Structural Comparison Between Search Methods:

  • Binary Search:
  • Data Precondition: Requires strictly sorted data.
  • Algorithmic Strategy: Divide and conquer.
  • Search Field Manipulation: Halves the search space on each step.
  • Time Complexity: Logarithmic growth ($O(\log(n))$).
  • Linear Search:
  • Data Precondition: Operates on unsorted or arbitrary data.
  • Algorithmic Strategy: Sequential exhaustive traversal.
  • Search Field Manipulation: Decrements search field by $1$ element at each step.
  • Time Complexity: Linear growth ($O(n)$).

• Worst-Case Search Comparisons Across Dataset Sizes:

  • When searching $n = 8\,\text{items}$:
  • Linear search requires up to $8\,\text{checks}$.
  • Binary search requires up to $4\,\text{checks}$.
  • When searching $n = 1,000\,\text{items}$:
  • Linear search requires up to $1,000\,\text{checks}$.
  • Binary search requires up to $10\,\text{checks}$.
  • When searching $n = 1,000,000\,\text{items}$:
  • Linear search requires up to $1,000,000\,\text{checks}$.
  • Binary search requires up to $20\,\text{checks}$.

Big O Notation and Algorithmic Complexity

• Historical Background of Big O Notation:

  • Big O notation predates digital electronic computing.
  • German mathematician Paul Bachmann first introduced the notation in 1894 within a treatise on analytic number theory.
  • Fellow mathematician Edmund Landau adopted and popularized the notation across the mathematics community beginning in 1909.
  • The letter 'O' represents the word "order" (Order of growth) (Tou, 2018).

• Purpose of Computational Complexity:

  • While an individual processor instruction executes in fractions of a microsecond, cumulative operations across large datasets compound drastically.
  • Password Brute-Force Metric: An algorithm executing an exhaustive brute-force search across every permutation of a $15\,\text{character}$ password requires over $500\,\text{years}$ to complete on a standard desktop computer (Craddock & Ellis, 2016, p. 94).

• Scope and Conceptual Boundaries of Big O:

  • What Big O Describes: Provides a standardized theoretical framework to classify algorithms by their worst-case asymptotic upper bound, denoted $O(x)$, where $x$ represents the upper limit growth rate (Craddock & Ellis, 2016, p. 94).
  • What Big O Does Not Tell Us: It does not calculate exact execution duration or wall-clock runtime in seconds. Instead, it predicts how execution time scales as input size $n$ expands from small inputs (e.g., $10$ elements) to massive scales (e.g., $10,000$ or $1,000,000$ elements) (Craddock & Ellis, 2016, p. 94).

• Hierarchy of Time Complexities (Ordered Slowest to Fastest Growing):

  • 1. Constant Complexity: $O(1)$
  • 2. Logarithmic Complexity: $O(\log(n))$
  • 3. Linear Complexity: $O(n)$
  • 4. Log-linear Complexity: $O(n \log(n))$
  • 5. Quadratic Complexity: $O(n^2)$
  • 6. Cubic Complexity: $O(n^3)$
  • 7. Exponential Complexity: $O(2^n)$
  • 8. Factorial Complexity: $O(n!)$

• Detailed Taxonomy of Complexity Classes:

  • Constant Complexity $O(1)$:
  • Execution duration remains invariant regardless of whether input size $n$ is small or vast.
  • Example: Accessing or updating an array element directly via its numerical index (arr[2]), or constant-time hashmap insertions.
  • Python array access (array_access.py): python names = ['james', 'alex', 'matthew', 'charlotte', 'daniel'] print(names[0]) # Accessing index 0 runs in O(1) names[2] = 'matt' # Mutating index 2 runs in O(1)       

• Logarithmic Complexity $O(\log(n))$:

  • Execution runtime grows much slower than the underlying dataset.
  • Execution increments by a single additional step each time the dataset size doubles.
  • Example: Binary search requires at most $3\,\text{comparisons}$ for $4\,\text{numbers}$, $11\,\text{comparisons}$ for $2,000\,\text{numbers}$, and $21\,\text{comparisons}$ for $2,000,000\,\text{numbers}$.

• Linear Complexity $O(n)$:

  • Execution runtime expands at the exact same proportional rate as input size.
  • Example: Accumulating a running sum of all items in an array via a single loop. A set containing $5\,\text{numbers}$ takes $5\,\text{steps}$; a set containing $100\,\text{numbers}$ takes $100\,\text{steps}$ (Craddock & Ellis, 2016, p. 95).

• Polynomial Complexity $O(n^x)$ ($x > 1$):

  • Runtime increases substantially faster than linear algorithms.
  • Quadratic ($O(n^2)$): Processing $1\,\text{item}$ requires $1^2 = 1\,\text{step}$; $10\,\text{items}$ require $10^2 = 100\,\text{steps}$; $100\,\text{items}$ require $100^2 = 10,000\,\text{steps}$.
  • Cubic ($O(n^3)$): Scales even more steeply, requiring $n^3$ operations (Craddock & Ellis, 2016, p. 95).

• Exponential Complexity $O(x^n)$ (e.g., $O(2^n)$):

  • Workload escalates at an explosive rate as input size increases.

  • An algorithm requiring $2^n$ steps needs $2^1 = 2\,\text{steps}$ for $1\,\text{value}$, $2^{10} = 1,024\,\text{steps}$ for $10\,\text{values}$, and $2^{100}\,\text{steps}$ for $100\,\text{values}$.

  • Evaluating $2^{100}$ produces a number with $31\,\text{digits}$, demanding trillions of years on conventional computers (Craddock & Ellis, 2016, p. 95).

  • Brute-Force Password Cracking Times:

• Theoretical duration required to test every permutation at an evaluation speed of $100,000,000,000\,\text{guesses per second}$ ($10^{11}\,\text{guesses/sec}$):

  • Length 6:

    • Numbers ($10\,\text{symbols}$): Instantly
    • Lowercase ($26\,\text{symbols}$): Instantly
    • Uppercase & lowercase ($52\,\text{symbols}$): Instantly
    • Letters & numbers ($62\,\text{symbols}$): $1\,\text{second}$
    • Letters, numbers & symbols ($95\,\text{symbols}$): $7\,\text{seconds}$

  • Length 8:

    • Numbers: Instantly
    • Lowercase: $2\,\text{seconds}$
    • Uppercase & lowercase: $9\,\text{minutes}$
    • Letters & numbers: $36\,\text{minutes}$
    • Letters, numbers & symbols: $18\,\text{hours}$

  • Length 10:

    • Numbers: Instantly
    • Lowercase: $24\,\text{minutes}$
    • Uppercase & lowercase: $17\,\text{days}$
    • Letters & numbers: $97\,\text{days}$
    • Letters, numbers & symbols: $19\,\text{years}$

  • Length 12:

    • Numbers: $10\,\text{seconds}$
    • Lowercase: $11\,\text{days}$
    • Uppercase & lowercase: $124\,\text{years}$
    • Letters & numbers: $1,022\,\text{years}$
    • Letters, numbers & symbols: $171,000\,\text{years}$

  • Length 14:

    • Numbers: $17\,\text{minutes}$
    • Lowercase: $20\,\text{years}$
    • Uppercase & lowercase: $335,000\,\text{years}$
    • Letters & numbers: $3.9\,\text{million years}$
    • Letters, numbers & symbols: $1.5\,\text{billion years}$

  • Impact When Data Size Doubts ($n \rightarrow 2n$):

• Constant $O(1)$: Workload remains invariant (stays identical).

• Logarithmic $O(\log(n))$: Workload increases by $1\,\text{step}$.

• Linear $O(n)$: Workload doubles ($\times 2$).

• Log-linear $O(n \log(n))$: Workload increases by just over double ($> 2\times$).

• Quadratic $O(n^2)$: Workload quadruples ($2^2 = 4\times$). If an algorithm requires $1\,\text{minute}$ for $1,000\,\text{items}$, it requires $4\,\text{minutes}$ for $2,000\,\text{items}$.

• Cubic $O(n^3)$: Workload increases eightfold ($2^3 = 8\times$).

• Exponential $O(2^n)$: Workload is squared ($(2^n)^2 = 2^{2n}$).

  • Algorithm Efficiency vs. Hardware Power Benchmark:

• Scenario: Processing $1,000,000,000\,\text{items}$ ($10^9\,\text{items}$) at a computing rate of $1,000,000,000\,\text{operations per second}$ ($10^9\,\text{steps/sec}$):

  • A log-linear algorithm ($n \log_2(n)$) finishes in approximately $30\,\text{seconds}$.
  • A quadratic algorithm ($n^2$) requires approximately $32\,\text{years}$.
  • Upgrading to hardware that is ten times faster reduces the quadratic runtime to roughly $3.2\,\text{years}$.
  • Core Principle: Algorithmic optimization always outperforms hardware speed upgrades.

Working with Big O

• Determining Big O from Source Code:

  • Analysis Rule: Identify the most active instruction inside the function, and determine how many times that line runs as dataset size expands to $n$.
  • Constant Time Implementation ($O(1)$):

  def first_item(items):
      return items[0]  # Runs exactly 1 time regardless of input size
      ```
  * **Linear Time Implementation ($O(n)$):**
  

  python def total(items): result = 0 for x in items: result += x # Loop body executes n times return result     ```

  • Quadratic Time Implementation ($O(n^2)$):

  def has_duplicate(items):
      for i in range(len(items)):
          for j in range(len(items)):
              if i != j and items[i] == items[j]:  # Executes n * n times
                  return True
      return False
      ```
  * **Logarithmic Time Implementation ($O(\log(n))$):**
  

  python def halvings(n): steps = 0 while n > 1: n = n // 2 # Value halves on each cycle, running log2(n) times steps += 1 return steps     ```

• Rules for Simplifying Big O Expressions:

  • 1. Retain only the fastest-growing term that dominates as $n \rightarrow \infty$.
  • 2. Omit all multiplicative constant factors and additive constants.
  • Simplification Examples:
  • Expression $3n + 2$ simplifies to $O(n)$: Multiplicative factor $3$ and constant $2$ do not influence asymptotic scaling.
  • Expression $n^2 + 5n + 7$ simplifies to $O(n^2)$: The quadratic term $n^2$ dominates. At $n = 1,000$, $n^2$ contributes $1,000,000$ out of the total $1,005,007\,\text{operations}$.
  • Expression $2^n + n^3$ simplifies to $O(2^n)$: Exponential growth quickly surpasses any polynomial term.
  • Expression $100$ simplifies to $O(1)$: Contains no $n$ variable; workload remains fixed for all inputs.

• Time and Space Complexity Profiles of Search Algorithms:

  • Linear Search:
  • Best-case Time Complexity: $O(1)$ (target found at index $0$)
  • Average-case Time Complexity: $O(n)$
  • Worst-case Time Complexity: $O(n)$
  • Worst-case Space Complexity: $O(1)$
  • Binary Search:
  • Best-case Time Complexity: $O(1)$ (target found at initial midpoint)
  • Average-case Time Complexity: $O(\log(n))$
  • Worst-case Time Complexity: $O(\log(n))$
  • Worst-case Space Complexity: $O(1)$

Practice Exercises and Review Questions

• Question 1: Array Length and Indexing:

  • Prompt: Let $B = [4, 8, 15, 16, 23, 42]$. What is $|B|$, and what is $B[3]$?
  • Answer: $|B| = 6$ (the total count of elements). $B[3] = 16$ (counting from index $0$: $B[0] = 4$, $B[1] = 8$, $B[2] = 15$, $B[3] = 16$).

• Question 2: Algorithm Selection on Unsorted Data:

  • Prompt: Which search would you use on an unsorted list of names, and why?
  • Answer: Linear search must be selected. Binary search cannot be applied because its divide-and-conquer logic requires sorted input.

• Question 3: Worst-Case Comparisons on 64 Items:

  • Prompt: A sorted list has $64\,\text{items}$. What is the most comparisons each search needs to find an item?
  • Answer: Linear search requires up to $64\,\text{comparisons}$. Binary search requires at most $7\,\text{comparisons}$ (halving chain: $64 \rightarrow 32 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$, which yields $6$ halving steps plus final evaluation, or $\log_2(64) + 1 = 7$ comparisons).

• Question 4: Big O Classification:

  • Prompt: Give the Big O time complexity of: accessing arr[3]; linear search; binary search.
  • Answer: Accessing arr[3] is $O(1)$; linear search is $O(n)$; binary search is $O(\log(n))$.

• Question 5: Trade-Off Analysis of Binary Search:

  • Prompt: Give one advantage and one disadvantage of binary search compared with linear search.
  • Answer:
  • Advantage: Requires vastly fewer comparisons when querying large collections ($O(\log(n))$ logarithmic scaling).
  • Disadvantage: Demands that the target dataset be sorted before searching.

• Question 6: Nested Loop Analysis and Simplification:

  • Prompt: A function has a loop over the whole list inside another loop over the whole list. What is its Big O, and what is $3n^2 + 2n$ simplified?
  • Answer: Nested loops over length $n$ run in $n \times n$ steps, producing $O(n^2)$. The polynomial $3n^2 + 2n$ simplifies to $O(n^2)$ by dropping the lower-order term $2n$ and constant coefficient $3$.

Independent Study and Bibliographic References

• Curated Independent Learning Resources:

  • Interactive Visualizer: Binary and Linear Search Visualisation (University of San Francisco Galles tool, cs.usfca.edu/~galles/visualization/Search.html).
  • Video Demonstration: Searching algorithms (BBC Teach class clips, bbc.co.uk/teach/class-clips-video/articles/z662pg8).
  • Instructional Guide: Extra reading on Big O notation (NeetCode, neetcode.io/courses/lessons/big-o-notation).
  • Video Lecture: Big O notation (YouTube, youtube.com/watch?v=kgBjXUE_Nwc&t=28).
  • Video Tutorial: Big O notation – a few examples (YouTube, youtube.com/watch?v=-Eiw_-v__Vo).
  • Interactive Game: Binary search interactive game (Math The Beautiful, maththebeautiful.com/binary-search).
  • Practical Exercises: Code breaker challenges – series 1 (101 Computing, 101computing.net/code-breaker-challenges).
  • Advanced Theory: P vs NP and computational complexity (YouTube, youtube.com/watch?v=pQsdygaYcE4).

• Subsequent Curriculum Preview:

  • Upcoming unit examines search and sort algorithms (Week 2, Lecture 2).
  • Focus topics: Utility of sorted data, algorithm tracing for bubble sort, insertion sort, merge sort, and quicksort using trace tables and pseudocode.
  • Comparison counting, best/worst case scenarios, algorithmic stability, and time complexity classifications.

• Academic References:

  • Craddock, G., & Ellis, V. (2016). Essential Maths Skills for AS/A Level Computer Science. Hodder Education.
  • European Space Agency. (2013, March 21). Planck reveals an almost perfect Universe. ESA Science & Exploration.
  • IFLScience. (2023, January 26). Computer scientist attempts to get the police to find his stolen bike using math.
  • Kehoe, C. (2025). The police won't investigate bike theft because there's too much CCTV to review. Why won't they adopt this simple mathematical trick? London Centric.
  • Tou, E. R. (2018). Math Origins: Orders of Growth. Mathematical Association of America.