Algorithm Analysis: Praxis Computer Science 5652
Algorithm analysis compares how an algorithm’s work grows as input size changes.
- State the algorithm, input case and cost being measured.
- Big O is an asymptotic upper bound, not automatically a worst-case label or an exact runtime.
- State input assumptions and distinguish the bound from the case.
On this page22 sections
- What algorithm analysis asks
- Describe growth with a bound and a case
- Linear and binary search
- Preprocessing changes the comparison
- Input size and constants matter
- Trace before comparing
- Avoid complexity shortcuts
- Quick reference
- Best, average and worst case use input distributions
- Account for the data structure
- State what you count
- Count operations in an original nested process
- Correctness is part of analysis
- Memory usage may change a choice
- Big O suppresses constants but they still matter practically
- Analyze recursive work with a recurrence
- Amortized cost summarizes sequences
- Use complexity to communicate trade-offs
- Count operations with an explicit input measure
- Read asymptotic notation as a growth statement
- Use a recurrence to reason about repeated work
- Distinguish time from space growth
What algorithm analysis asks
Algorithm analysis studies how the steps or resources of an algorithm grow as input size changes. It helps compare approaches, explain trade-offs and reason about scale. It does not by itself predict exact seconds on a particular machine.
For Praxis 5652, connect the analysis to a specific task and assumption: searching an unsorted list, searching an ordered array, sorting records or traversing a structure. State the input case and algorithm variant.
Describe growth with a bound and a case
Big O notation expresses an asymptotic upper bound under the analysis being made. It is not synonymous with worst case in every statement; the bound type and input case are separate choices. Omega can express a lower bound and Theta a tight bound when both sides are established.
For example, a search's best, average and worst cases describe input positions or patterns. A bound describes how a chosen cost grows. Keep these questions distinct when reading a claim.
Linear and binary search
A linear scan checks entries one after another and can work without ordering. Its work grows in proportion to the list length in the worst case. Binary search repeatedly halves the remaining search interval, but requires ordered data and a way to inspect the middle efficiently.
On a sorted array of 1,024 entries, binary search needs roughly ten halvings to isolate one position, whereas an unsuccessful linear search can inspect every entry. Exact comparisons depend on implementation and whether the target appears.
Preprocessing changes the comparison
Sorting a collection has a cost. If you need one search, scanning once may be cheaper than sorting then searching. If you need many searches and the collection remains stable, paying to sort once can be useful.
An index or maintained sorted structure also has creation and update costs. Analyze the whole workflow: construction, queries, insertions, deletions and memory, rather than selecting a method from one operation alone.
Input size and constants matter
Asymptotic notation emphasizes growth for large inputs and abstracts away constant factors. For small data, a straightforward method can be faster or easier to maintain. Real performance also depends on memory access, implementation, hardware and data distribution.
Use Big O to understand scaling and choose reasonable designs, not to claim an exact runtime. A statement such as O(n log n) should specify what algorithm and input assumptions it describes.
Trace before comparing
Count the relevant operations in a small example, then identify how the count changes as input grows. For nested loops, inspect whether the inner loop always runs n times or whether its bound changes with the outer index.
A triangular loop might run 1 + 2 +... + n steps, which grows quadratically even though the total is not exactly n squared. Simplify constants and lower-order terms only after identifying the growth.
Avoid complexity shortcuts
Do not infer the complexity from the number of lines of code or from a single test input. Recursion, data structure choice and early exit conditions can affect work. Best, average and worst case depend on how inputs relate to the algorithm.
In study notes, record algorithm, input size, case and cost being measured. This prevents a correct bound from being attached to the wrong claim.
Quick reference
| Task | Method assumption | Growth intuition |
|---|---|---|
| Find one item in unsorted list | No ordering needed | Linear scan |
| Find in ordered array | Random access to middle | Repeated halving |
| Many searches | Include preprocessing and updates | Whole workflow cost |
| Compare runtimes | State case and operation | Growth, not exact seconds |
Best, average and worst case use input distributions
Best case describes the most favorable inputs for a chosen algorithm, worst case the least favorable, and average case depends on a defined distribution or expectation. These are case choices, not synonyms for O, Omega or Theta.
Linear search's best case finds the target first; its worst case reaches the end or misses. A bound should be attached to the stated case.
Account for the data structure
Binary search on an array can access its midpoint directly. On a linked list, reaching the midpoint can itself require traversal, so the same comparison strategy does not have the same access cost.
When selecting an algorithm, include operations supported by the structure, such as indexing, insertion and deletion.
State what you count
Complexity can refer to time, comparisons, memory, recursive calls or another resource. For a recursive algorithm, include stack use if memory matters.
A concise analysis names input size, operation and case. Without those, even familiar notation can be misleading.
Count operations in an original nested process
Suppose an outer loop runs n times and, on each pass, an inner loop runs n times. The body executes n multiplied by n, or n squared, times. If the inner bound grows with the outer index, sum the sequence rather than assuming a fixed square.
Write the first few counts, find the pattern, then express the total growth. This shows where a complexity claim comes from.
Correctness is part of analysis
An algorithm that is fast but returns a wrong value for duplicates or empty input is not a valid solution. Define the result and test important cases before comparing efficiency.
Use invariants to explain why each step preserves the possibility of a correct result.
Memory usage may change a choice
An algorithm may use extra arrays, recursion stack or an index to improve time. A memory-constrained system can prefer a slower in-place method.
State whether the question asks about time or space. Do not equate fewer instructions with lower total resource use.
Big O suppresses constants but they still matter practically
An algorithm with O(n squared) growth can outperform an O(n log n) method for very small n because constants, implementation and setup differ. For large inputs, growth rates become more important.
Use the asymptotic comparison to understand scaling; use benchmarks and requirements for a real system choice.
Analyze recursive work with a recurrence
A recursive algorithm can divide a problem and make smaller calls. To understand its growth, identify the number and size of subproblems and the work done at each level.
For a simple recurrence T(n)=T(n/2)+constant, repeated halving produces logarithmic depth. More complex recurrences need the exact structure; do not guess from the word “recursive.”
Amortized cost summarizes sequences
An operation that occasionally triggers expensive rebuilding can still have a modest average cost across a long sequence. The amortized view is not the same as average-case input distribution.
When comparing dynamic arrays or indexes, include the sequence of updates and queries rather than analyzing only one costly event.
Use complexity to communicate trade-offs
An algorithm comparison should mention correctness, growth, memory and relevant workload. A simpler method can be preferred when inputs are small or maintenance matters more than asymptotic speed.
This is a design choice, not a universal ranking. Tie the recommendation to stated constraints.
Count operations with an explicit input measure
Complexity analysis begins by naming the input size. For a list search, n is the number of elements. A single scan may inspect up to n entries, so its work grows in proportion to n. Binary search repeatedly halves a sorted range, requiring about log base two of n comparisons.
If n is 1,024, repeated halving reaches a single candidate in about ten steps because 2 to the tenth power is 1,024. That count describes growth, not an exact wall-clock time: memory layout, implementation, comparison cost and fixed overhead also matter.
Read asymptotic notation as a growth statement
Big O gives an upper growth bound under the stated model; Big Omega gives a lower bound; Big Theta gives a tight asymptotic bound when both apply. These notations do not by themselves specify which input case is being analyzed. An algorithm can have a worst-case and an average-case analysis, each described with a bound.
For a scan, best-case work can be constant if the first element matches, while worst-case work grows with n. Saying “the scan is O(n)” often summarizes an upper bound, but it does not mean every run inspects n items.
Use a recurrence to reason about repeated work
A divide-and-conquer algorithm can split a problem into smaller parts, solve them and combine results. A recurrence describes how much work is done at size n plus the work on smaller inputs. For a binary search, each step performs constant comparison work and leaves roughly half the input, producing logarithmic depth.
For a recursive algorithm, also check the base case and whether every recursive call moves closer to it. A correct recurrence does not prove the implementation terminates if a branch can repeat the same input size.
Distinguish time from space growth
An algorithm can save time by using additional memory. A hash table can support fast average lookup under suitable assumptions, but it uses storage and collision handling. A merge-based sort has predictable growth but normally allocates auxiliary space proportional to the input. An in-place method may reduce extra storage while changing stability or performance properties.
When a prompt asks for an efficient method, identify the constrained resource. For a memory-limited device, an extra array may be unacceptable. For an interactive classroom tool, predictable response time may matter more. State whether the comparison concerns time, auxiliary space or both.
Common questions
Is Big O always worst case?
No. Big O is an upper bound; case selection is a separate question.
Does Big O predict exact seconds?
No. It describes growth, not an exact runtime on specific hardware.
Does binary search work on any list?
It requires ordered data and suitable access to middle elements.