Why is mathematics important in computer algorithms? Because a program can be correct on ten items and still become unusable on ten million. Mathematics gives us a language for describing how work grows with input size, comparing methods without tying the answer to one laptop, and proving that a shortcut has not silently skipped the result we need.
Binary search is a beautiful example. A linear search may inspect every item in a list. Binary search repeatedly halves a sorted search interval. That one change turns a million-item worst case from roughly a million comparisons into about twenty. The gain comes from order, powers of two and a carefully maintained logical invariant—not from typing faster code.
This article explains Big-O complexity, linear and binary search, divide-and-conquer reasoning, sorting, time–space trade-offs and benchmarking. It keeps an important boundary in view: an asymptotic class is not a stopwatch result, and a fast algorithm is not automatically correct, fair, secure or appropriate for the data.
Choose the algorithm question you want to solve
- How does work grow? Start with input size, operations and asymptotic notation.
- Why is binary search fast? Follow a sorted interval as it is cut in half.
- When is sorting worth the cost? Compare one search with many repeated searches.
- What does Big-O leave out? Examine constants, hardware, memory and real data.
- How do I know an algorithm is correct? Use invariants, boundary cases and tests.
- What can a student build? Measure search and sorting methods with reproducible experiments.
An algorithm is a finite method, not merely code
An algorithm is a defined procedure for transforming an input into an output. Code is one implementation of that procedure in a programming language. The distinction matters because the same algorithm can be written in Python, Java, C or pseudocode, while two programs in the same language can use fundamentally different algorithms.
Consider the task “find a name in a list.” One method begins at the first item and checks names in order. Another, available when the list is sorted, checks the middle name and discards half of the remaining interval. Both can be coded correctly. Their growth behaviour is different.
Before measuring efficiency, define the task. Are duplicate names allowed? Should the method return the first match, any match or the number of matches? What happens if the name is absent? Is the list already sorted? A vague problem produces a vague performance claim.
Input size gives growth a horizontal axis
Complexity analysis needs a measure of input size, usually written \(n\). For a list problem, \(n\) may be the number of items. For a graph, size may require both vertices \(V\) and edges \(E\). For integer arithmetic, the number of bits can matter more than the numerical value itself.
Choosing \(n\) carelessly can hide work. Adding two 10-digit integers and adding two million-digit integers are both one “addition” in a high-level expression, but the underlying computation differs. A truthful model names the unit whose growth drives the cost.
Size does not describe every property. Two arrays of length 10,000 can have different order, duplication or value distributions. Those features can change best-case or average behaviour even when \(n\) matches.
Count meaningful operations before counting seconds
Wall-clock time depends on processor, programming language, compiler, memory, operating system and other running tasks. Mathematical analysis first counts a representative operation such as comparisons, swaps, arithmetic steps, memory accesses or messages.
For linear search, comparisons are a natural count. If the target is first, there is one comparison. If it is last or absent, there can be \(n\). If target positions are equally likely and the item is present exactly once, the expected number is \((n+1)/2\).
The count is a model. A comparison of short integers may cost less than comparing very long strings. Reading an item from nearby cache may cost less than fetching it from slow storage. The model is valuable when its simplifications are stated.
Big-O describes an asymptotic upper bound
The U.S. National Institute of Standards and Technology defines \(f(n)=O(g(n))\) when positive constants \(c\) and \(k\) exist such that \(0\le f(n)\le c g(n)\) for all \(n\ge k\). The constants must not depend on \(n\).
Informally, beyond some sufficiently large size, \(g(n)\) multiplied by a fixed constant bounds the growth of \(f(n)\). Thus \(3n+20\) is \(O(n)\): for example, it is at most \(5n\) whenever \(n\ge10\).
Big-O does not mean “exactly equal.” The function \(3n+20\) is also \(O(n^2)\), because a quadratic eventually bounds it. When we want matching upper and lower growth, \(\Theta(n)\) is the more precise statement.
Common informal classes include constant \(O(1)\), logarithmic \(O(\log n)\), linear \(O(n)\), linearithmic \(O(n\log n)\), quadratic \(O(n^2)\) and exponential \(O(2^n)\). Their practical ordering can change for small inputs, but their long-run shapes differ dramatically.
Constants disappear from the class but not from the machine
Suppose method A uses \(1000n\) operations and method B uses \(n^2\). A has linear growth and B quadratic growth. Yet at \(n=10\), A’s model gives 10,000 operations and B gives 100. B can be faster at small sizes despite the less favourable class.
The crossover occurs when \(1000n=n^2\), so \(n=1000\) for positive \(n\). Beyond that point the quadratic term becomes larger. The example explains why asymptotic analysis guides scaling but does not replace measurement.
Lower-order terms can matter too. A count such as \(n^2+100n+50\) is \(\Theta(n^2)\), because the square dominates for sufficiently large \(n\). At classroom-sized inputs, the other terms may still be visible.
Linear search is simple and sometimes exactly right
Linear search checks items one by one until it finds the target or reaches the end. It needs no sorted order and works on an incoming stream. Its worst-case comparison count is \(n\), so its worst-case time is \(\Theta(n)\) under the simple comparison model.
For a five-item list [12, 4, 19, 7, 15], searching for 7 checks 12, 4, 19 and then 7: four comparisons. Searching for 9 checks all five before reporting absence.
The method has useful strengths. It has tiny setup cost, preserves original order, works on linked or sequential data and can stop early. If a list contains only six items and will be searched once, building an elaborate index may be wasteful.
Efficiency should therefore be tied to a workload. “Binary search is better” is incomplete. Better for which data, preparation cost, number of queries, update pattern and memory constraint?
Binary search buys speed with sorted order
Binary search works on a sorted array or another structure that supports efficient access to the middle. The method keeps a search interval from index low to index high, checks the middle item, and retains only the half that could still contain the target.
The NIST Dictionary of Algorithms and Data Structures describes it as repeatedly dividing a sorted search interval in half until the value is found or the interval becomes empty. Its comparison growth is logarithmic.
For the sorted list [3, 8, 12, 17, 21, 26, 31, 40, 55, 63, 72, 89, 94, 101, 120], search for 89. The middle item is 40, so discard the lower half. In the remaining upper half, the middle is 89, so the search ends after two comparisons.
Search for 90 instead. The method checks 40, then 89, then 101, then 94, and eventually reaches an empty interval. Absence is established without inspecting every item.
Halving creates the logarithm
After one unsuccessful comparison, at most about \(n/2\) candidates remain. After two, \(n/4\) remain. After \(k\), roughly \(n/2^k\) remain. The process ends when this quantity is at most one.
Solve \(n/2^k\le1\). This means \(2^k\ge n\), so \(k\ge\log_2 n\). The worst-case number of comparisons is therefore proportional to \(\log_2 n\).
Powers of two make the effect easy to see. Doubling \(n\) adds only about one comparison. A list of 1,024 items needs at most about 10 halving decisions; 1,048,576 items need about 20; more than a billion items need about 30 under the ideal model.
This is why logarithms matter in computing. They count how many times a quantity can be multiplied or divided by a fixed factor before reaching a threshold.
A loop invariant explains correctness
Speed is worthless if the method discards the target. A loop invariant is a statement that remains true before and after every iteration. For binary search, a useful invariant is: if the target occurs in the array, at least one occurrence lies inside the current search interval.
The invariant is true initially because the interval covers the whole array. If the middle value is less than the target, sorted order proves that every earlier value is also too small; setting low beyond the middle preserves the invariant. The upper-half argument is symmetric.
When the interval becomes empty, the invariant implies the target is absent. When the middle matches, the output is valid. This proof has three parts: initialise the invariant, preserve it, and connect termination to the result.
Students often learn algorithms by tracing examples. Traces are useful tests, but they do not cover every possible input. An invariant turns the reason into a reusable proof.
Boundaries cause many binary-search bugs
Should high be the last valid index or one position after it? Is the interval closed [low, high] or half-open [low, high)? Both conventions work, but mixing them causes skipped values, repeated intervals or out-of-range access.
Under a closed interval, the loop usually continues while low <= high. After a too-small middle, update to low = mid + 1; after a too-large middle, use high = mid - 1. Reusing mid without the plus or minus one can prevent progress.
NIST notes another implementation detail: computing mid = (low + high)/2 can overflow a fixed-width integer when both bounds are large. low + (high - low)/2 represents the same midpoint for non-negative bounds without that addition overflow.
Test empty arrays, one item, two items, first and last positions, absent values below and above the range, and duplicates. Edge cases are not annoying exceptions; they are where the interval definition becomes visible.
Duplicates change the requested answer
Ordinary binary search may return any matching occurrence. If the task asks for the first occurrence, finding a match is not the end: record it and continue searching the lower half. For the last occurrence, continue in the upper half.
These variants find boundaries in \(O(\log n)\) time. The number of duplicate items can then be computed from the last and first indices plus one, without scanning the entire duplicate block.
The example teaches a larger lesson. Complexity belongs to a precisely defined output. “Find a value,” “find the first value,” and “count all values” are related but different problems.
Sorting can be an investment for repeated searches
Binary search requires order. If data are unsorted, sorting has a cost, often \(O(n\log n)\) for a comparison-based general-purpose method. One binary search after sorting may therefore cost more overall than one linear search.
Suppose there are \(q\) searches. Linear search costs on the order of \(qn\). Sorting once and then using binary search costs roughly \(n\log n+q\log n\). As \(q\) grows, preparation can pay for itself.
For \(n=1,000,000\), \(\log_2 n\) is about 20. Sorting might require tens of millions of comparisons, while each later search uses about twenty. Whether this is worthwhile depends on how many queries occur and how often the data change.
If new items arrive constantly, maintaining a sorted array can require costly movement. A balanced search tree, hash table or database index may better match the update–query pattern. Data structure and algorithm should be chosen together.
Sorting algorithms reveal different growth patterns
Selection sort repeatedly finds the smallest remaining item. It makes roughly \(n(n-1)/2\) comparisons, which is \(\Theta(n^2)\). Doubling input size makes the dominant comparison count about four times larger.
Merge sort divides a list into halves, sorts the halves recursively and merges them. There are about \(\log_2 n\) division levels, and merging across each level processes \(n\) items. The total is \(\Theta(n\log n)\).
Quicksort partitions items around a pivot. Its average behaviour under suitable conditions is \(\Theta(n\log n)\), but poor pivot behaviour can produce \(\Theta(n^2)\) worst cases. Practical implementations use careful pivot strategies, small-array methods and introspective safeguards.
No single label captures stability, extra memory, worst-case guarantees, adaptiveness to existing order or cost of moving large records. “Fastest sort” needs a workload and a measurement definition.
A merge-sort recurrence mirrors the program
If sorting \(n\) items means sorting two halves and merging in linear work, a recurrence is
\[ T(n)=2T(n/2)+cn. \]
At the top level, merging costs \(cn\). The next level has two merges of size \(n/2\), whose total is again \(cn\). This repeats for approximately \(\log_2 n\) levels, giving about \(cn\log_2 n\) plus base-case work.
A recursion tree makes this visible. Each row represents a scale; the row’s combined work remains proportional to \(n\). Multiplying work per row by number of rows produces \(n\log n\).
The method is not limited to sorting. Divide-and-conquer geometry, fast transforms and parallel algorithms use similar recurrences, sometimes with different numbers of subproblems or combination costs.
Comparison sorting has a lower-bound story
There are \(n!\) possible orders of \(n\) distinct items. A comparison has two possible outcomes in a simplified decision tree. To distinguish all permutations, the tree needs at least \(n!\) leaves and therefore height at least \(\log_2(n!)\), which grows as \(\Omega(n\log n)\).
This means a general comparison sort cannot guarantee better than order \(n\log n\) comparisons for every input. The claim applies to the comparison model. Counting sort and radix methods can use information about keys rather than only pairwise comparisons and operate under different assumptions.
Lower bounds are valuable because they change the question. If a method already matches the bound in its model, improvement may require a different model, additional structure, approximation, parallelism or a better constant—not a wish for a comparison sort with impossible general growth.
Time complexity and space complexity can trade places
An algorithm may become faster by storing an index, memo table or lookup structure. Hash-based lookup can be constant expected time under suitable assumptions, but the table uses memory and has construction and collision costs.
Merge sort commonly uses auxiliary storage for merging. An in-place method may use less extra memory but perform more data movement or have a more complex implementation. On a memory-limited device, space can be the binding constraint.
Input storage should be distinguished from extra or auxiliary space. A program that receives an array already needs room for the array. Space complexity often asks how much additional memory grows because of the algorithm.
Recursion also uses a call stack. Binary search written recursively has logarithmic stack depth, while an iterative version can use constant extra control space. The high-level time class remains logarithmic.
Average case needs a probability model
Saying an algorithm is “fast on average” is incomplete without a distribution over inputs or random choices. Linear search’s average comparison count of \((n+1)/2\) assumes a present target is equally likely at every position. If popular items are placed first, the real average can be much smaller.
Randomised quicksort analyses make assumptions about pivot selection rather than assuming real input orders are uniformly random. Hash-table expected performance depends on hashing and load behaviour. An adversarial or highly clustered workload can violate a casual average claim.
Worst case provides a guarantee; average case can reflect typical use; best case shows an opportunity to stop early. A responsible report states which one it is using.
Big-O is not a benchmark
Two \(O(n\log n)\) implementations can have different constants, memory access patterns and parallel behaviour. Cache-friendly contiguous access can outperform pointer chasing even when abstract operation counts look similar.
Benchmarks complement analysis. They should use multiple input sizes, repeated runs, controlled environments and clearly described data. Warm-up effects, compilation, random seeds, disk caching and background work can distort timing.
Plot time against \(n\), \(n\log n\) and \(n^2\). If doubling \(n\) roughly doubles time, linear growth is plausible over the measured range; if it quadruples, quadratic growth is plausible. A short range cannot prove an asymptotic theorem, but it can reveal implementation behaviour.
Use a checksum or verified output so an apparently fast program is not merely omitting work. Performance testing without correctness testing rewards the wrong thing.
Algorithm choices affect people and systems
An efficient ranking, allocation or classification procedure may still use biased data or an unsuitable objective. Complexity analysis asks how resources scale; it does not certify the social meaning of the result.
Resource costs can nevertheless have social consequences. An unnecessarily expensive algorithm uses more energy, money or latency and may exclude users with slower devices or connections. A design that scales can make a service more accessible, provided quality and safeguards are preserved.
Security can change the preferred implementation. Some cryptographic operations avoid data-dependent timing because variable execution can leak information. The fastest ordinary routine may not be the safest routine for secrets.
Common misconceptions
“Big-O tells me exactly how many seconds a program takes”
It describes growth under a model. Seconds require implementation and hardware measurements.
“O(n²) is always slower than O(n)”
Not for every small input or constant. The growth advantage emerges as size increases.
“Binary search works on any list”
It needs an ordering compatible with the comparisons and efficient access to the interval’s middle.
“Logarithmic means one step”
The number grows slowly but still grows. A million items need about twenty halvings, not one.
“If code passes examples, it is proven correct”
Examples can reveal errors but cannot cover all inputs. Invariants and boundary reasoning explain why the method works generally.
“The fastest algorithm uses the least memory”
Time and space often trade. Indexes, caches and memoisation spend memory to save work.
“Average case means the average of my last few runs”
Mathematical average-case analysis requires an explicit probability model. Empirical averages require a defined workload and sound measurement.
A six-week algorithm mathematics project
Week 1: define the search contract
Specify input type, target, duplicate policy and absent result. Write linear search and test boundary cases.
Week 2: trace binary search
Use sorted cards or a spreadsheet. Record low, mid, high, comparison and retained interval after every step.
Week 3: prove the invariant
Explain why the target, if present, remains in the interval. Check termination for empty, one-item and two-item intervals.
Week 4: count rather than guess
Generate several sizes and count comparisons for present and absent searches. Compare with \(n\) and \(\lceil\log_2 n\rceil\).
Week 5: include preparation
Time one linear search, sorting plus one binary search, and sorting plus many binary searches. Identify the crossover in the tested environment.
Week 6: communicate limits
Present growth plots, correctness checks and caveats. Explain why one benchmark does not establish universal superiority.
Guidance for students and families
Students can begin without advanced programming. Use a phone book, sorted cards or a “guess my number” game to experience halving. Then translate each decision into an interval update.
Parents can ask, “What information lets you discard half?” That question directs attention to structure. The answer is not simply “because binary search does that”; it is “because sorted order proves that half cannot contain the target.”
Encourage hand traces before optimisation. Most binary-search mistakes are boundary mistakes. A table of low, mid and high often makes the error visible faster than staring at code.
Students should keep correctness and performance separate. First establish the output rule and test it. Then count operations and benchmark. This order builds trustworthy problem-solving habits.
Careers and pathways
Algorithmic reasoning appears in software engineering, data engineering, cybersecurity, operations research, scientific computing, robotics, finance, logistics and digital-product design. Roles differ in qualifications and daily work; mathematics alone does not guarantee admission or employment.
A strong foundation includes algebra, functions, logarithms, proof, probability, discrete mathematics, data structures and programming. Communication matters too: engineers must explain why a method scales, what assumptions it uses and what failure cases remain.
Students can keep options open by building small verified projects rather than chasing a fashionable language. The transferable skill is learning to define a problem, choose a model, prove a method and compare it honestly.
Did You Know? Doubling can add only one comparison
For ideal binary search, moving from \(2^k\) to \(2^{k+1}\) items adds roughly one halving step. That is why ordered structure can turn enormous lists into manageable search paths.
Did You Know? Big-O is an upper bound, not an equality sign
NIST notes that Big-O is often misused to mean exact order. \(\Theta\) is the notation for a matching asymptotic order when both upper and lower bounds hold.
Did You Know? A tiny midpoint formula can prevent overflow
low + (high - low)/2 avoids the potentially overflowing addition in (low + high)/2 for non-negative fixed-width indices. Mathematical equivalence does not always mean identical machine behaviour.
Frequently asked questions
What is algorithmic complexity?
It describes how a chosen resource, such as time or memory, grows as input size grows under a stated model.
What does O(n) mean?
It means the resource is eventually bounded above by a constant multiple of \(n\). It does not give an exact time.
Why is binary search O(log n)?
Each comparison discards about half the remaining candidates, so the number of steps is how many halvings reduce \(n\) to one.
Must a list be sorted for binary search?
Yes, or it must have an equivalent monotone ordering property that proves which side can be discarded.
Is binary search always better than linear search?
No. Linear search can be preferable for tiny, unsorted, streaming or one-use data. Include sorting and maintenance costs.
What is the difference between O and Theta?
Big-O is an asymptotic upper bound. Theta gives a matching upper and lower order.
Why analyse space as well as time?
Memory, bandwidth and cache behaviour can be limiting resources. A faster method may use more storage.
Can benchmarks replace mathematical analysis?
No. Benchmarks show particular implementations on particular workloads; analysis explains growth and guarantees. Use both.
Useful next reading
The NIST definition of Big-O notation states the formal upper-bound condition and explains why computation models matter. The NIST binary-search entry describes interval halving, logarithmic runtime and a safe midpoint expression.
Continue into Why Mathematics? | Graph Theory, Networks and Internet Routing for path algorithms, Why Mathematics? | Data Compression, Entropy and Huffman Coding for greedy coding trees, and Why Mathematics? | Machine Learning, Loss Functions and Gradient Descent for iterative optimisation.
The How Computer Science Works master guide places algorithms beside programming, data, networks and software systems.
Final perspective
Online algorithms decide before all data arrive
Many textbook problems assume the complete input is available. Streaming and online settings are different: observations arrive over time, storage may be limited, and a decision may be required before the future is known.
An online method can be compared with an ideal offline method that sees the entire sequence. Competitive analysis studies the ratio between their costs under defined conditions. The comparison does not predict an exact future; it measures how much uncertainty can hurt a decision rule.
Running averages offer a simple example. After n observations with mean mₙ, a new value x updates the mean as:
mₙ₊₁ = mₙ + (x − mₙ)/(n+1).
This needs only the current mean and count rather than storing every value. It is mathematically efficient in space, though it cannot reconstruct the original sequence. The lost information is a deliberate trade-off.
Randomised algorithms make probability part of the contract
Some algorithms use random choices to simplify design or improve expected performance. A random pivot in quicksort can reduce the chance of repeatedly producing extremely unbalanced partitions when inputs are not adversarially aligned with the random source.
Randomisation does not mean “anything can happen, so analysis is impossible”. We can calculate expected cost, tail probabilities and failure chances under an explicit model. We can also repeat an independent randomised test to reduce error probability when the method allows it.
A report should distinguish a Las Vegas algorithm, which always returns a correct answer but has random running time, from a Monte Carlo algorithm, which uses bounded time but may have a stated error probability. The names describe guarantees, not programming style.
Complexity should include data movement
On modern machines, moving data between memory levels can cost more time and energy than a simple arithmetic operation. Two algorithms with the same asymptotic operation count may behave differently because one accesses memory sequentially while another jumps unpredictably.
This does not invalidate Big-O. It shows that the cost model must match the question. Cache-aware and external-memory analyses count transfers between memory levels, while distributed systems may count messages and communication volume.
Students can observe the idea without specialised hardware by timing a sequential scan and contrasting it with scattered accesses, while treating the result as machine-specific evidence. The deeper lesson is that an “operation” is a modelling choice.
Before closing, connect the individual techniques into a complete decision process. Algorithm analysis is not a contest to name the smallest Big-O class first. It is a structured comparison of contracts, inputs, costs and evidence.
A practical algorithm-selection checklist
Begin with correctness. Write what counts as a valid output, what inputs are permitted, how duplicates are handled and what happens when the target is absent. A fast program that returns the wrong index or silently drops a result has not solved the problem.
Next, identify the resource that matters. A mobile application may care about battery and memory. A server may care about high-percentile latency rather than average throughput. A classroom exercise may count comparisons so growth remains visible. “More efficient” is incomplete until the resource and workload are named.
Then describe scale and distribution. Is the list already sorted? Will it be searched once or a million times? Does it fit in memory? Are additions frequent? Are keys uniform, clustered or adversarial? Those facts determine whether preparation costs and average-case assumptions are reasonable.
Compare growth classes and constants. Use asymptotic analysis to understand scaling, then use representative benchmarks to observe implementation and hardware effects. Analysis extrapolates structure; measurement tests the actual system.
Finally, examine zero length, one item, repeated keys, extremes and malformed inputs. If an algorithm influences a live service, include monitoring and recovery. This connects mathematical reasoning to responsibility.
Amortised analysis explains occasional expensive operations
Some data structures perform a costly operation only occasionally. A dynamic array may allocate a larger block and copy existing elements when capacity is exhausted. One insertion can therefore cost proportional to the current length although most insertions are constant-time.
If capacity doubles whenever it fills, total copying across many appends forms a geometric series:
1 + 2 + 4 + ··· + 2ᵏ < 2ᵏ⁺¹.
When final capacity is on the order of n, total copying over n appends is also on the order of n. Spread across all appends, the amortised cost per append is constant.
“Amortised” does not make the expensive step disappear. A real-time system may still care about the worst individual pause, while a throughput-oriented application may accept the sequence guarantee.
Hash tables reveal expected-case assumptions
A hash table maps keys into positions or buckets. Under suitable assumptions about distribution and load, lookup can have expected constant-time behaviour. Collisions are unavoidable when many possible keys map into a finite table, so the implementation must resolve them through chaining, probing or another strategy.
If many keys cluster, performance can deteriorate toward linear behaviour. Resizing also creates occasional large costs, which can be analysed amortised across operations.
This contrasts with binary search. Binary search gives logarithmic comparisons on sorted random-access data. A hash table may offer faster expected lookup but gives up sorted order and depends on hashing quality and load control. The correct choice follows the required operations.
Recursion trees make divide-and-conquer visible
For T(n) = 2T(n/2) + cn, the top level performs cn non-recursive work. The next level has two subproblems of size n/2, so combined work is again cn. This continues for about log₂n levels.
Work per level multiplied by the number of levels gives approximately cn log₂n, with leaves adding a linear term. Overall growth is Θ(n log n).
Drawing the tree prevents a common mistake: counting only depth and forgetting the growing number of subproblems. It explains why divide-and-conquer remains efficient when each level performs only linear combined work.
Complexity can use several input variables
Not every input has one natural size. A graph algorithm may depend on vertices V and edges E. A matrix operation may depend on rows m and columns n. Text search may depend on document and pattern lengths.
Writing O(V + E) preserves information lost by forcing both into n. A sparse graph has far fewer edges than a dense graph, so instances with equal vertex counts can require different work.
Multi-parameter analysis is more honest. It shows that “input size” is a modelling decision, and the best variables mirror the structure driving operations.
Lower bounds prevent impossible promises
An upper bound limits how quickly cost grows beyond a threshold. A lower bound can show that every algorithm in a defined model needs at least a certain amount of work.
For comparison sorting, a decision tree must distinguish n! possible orders. A binary tree needs height at least log₂(n!), which grows as Ω(n log n). Merge sort therefore reaches the optimal asymptotic comparison class within that model.
“Within that model” matters. Counting sort and radix methods exploit extra structure, so they are not contradictions. Lower bounds are conditional statements, not universal bans.
Write a short complexity report
State the task and representation. Present clear pseudocode. Prove correctness with an invariant or induction. Count a representative operation in best, worst and justified expected cases. Analyse auxiliary space separately. Test several scales and explain agreement or disagreement with the model.
A strong conclusion is conditional: “For repeated membership queries on a static sorted array, binary search reduced comparison growth from linear to logarithmic; for one query on a tiny unsorted list, sorting first cost more than scanning.” Evidence, conditions and decision belong together.
Algorithm mathematics asks two questions together: does the method work, and how does its cost grow? Binary search answers both through sorted order, a shrinking interval and a logarithm. Big-O then lets us compare growth without pretending constants and machines do not matter.
That combination—definition, proof, model and measurement—is the real benefit of learning mathematics for computing. It helps a student move from “the program ran” to “the program is correct for a reason, and I understand where it will still work when the data become large.”