COMP5112 Chap.1 Algorithm Design and Growth Rates
Algorithm Design and Growth Rates
From a problem to a defensible algorithm
This chapter separates computational problems, algorithms and programs, then shows why test cases cannot prove correctness. It develops worst-case running-time functions, asymptotic upper bounds and the simplification rules that remove constants and lower-order terms only after the operation count is justified.
Worked traces connect loop ranges to linear, logarithmic, linearithmic and quadratic growth, with special attention to nested ranges that shrink rather than execute a full square.
Begin every analysis by naming the input size and the operation being counted. A loop that visits n records twice contributes two linear terms; it does not become quadratic merely because two passes appear in the code.
Nested loops need their actual ranges. When the inner bound depends on the outer index, write the resulting sum. A triangular range produces n times n minus one divided by two, while repeatedly halving a candidate set produces a logarithm. These derivations turn a complexity label into an argument.
Worst-case analysis compares all permitted instances of the same size and chooses the largest operation count.
The worst input is therefore defined by algorithmic decisions, not by visually large values. For a search it may place the target last or omit it; for a sort it may maximise comparisons or moves depending on the stated measure. Keep the measure explicit because an arrangement that maximises swaps need not maximise comparisons.
Once a function is derived, retain the fastest-growing term and discard fixed multipliers for asymptotic comparison.
Correctness is a separate obligation. Testing several inputs can reveal a defect but cannot cover every allowed instance. A proof-style explanation states what is true before an iteration, shows that one iteration preserves that property, and establishes progress toward termination.
The final state then connects the invariant to the required output. For recursive algorithms, identify a smaller subproblem and a base case. These habits also improve debugging because they reveal the first state where the claimed property stops holding.
Big-O supplies an upper bound and can be loose. Saying that a linear function is O of n squared is true but unhelpful when comparing designs.
In course answers, derive a tight familiar class from the count and explain the consequence of growth. Doubling n roughly doubles linear work, quadruples quadratic work, and adds a fixed amount to a base-two logarithmic count.
Those are scaling statements rather than predictions of seconds, since implementation and hardware constants still affect small instances.
A reliable exam response follows one compact chain: define n, identify the basic operation, form the count or recurrence, simplify it, and interpret the result.
For sequential phases, add their costs; for independent repeated ranges, multiply only when the bounds justify it; for recursive work, account for both the number and size of calls. Finish by checking preconditions and output contracts before comparing two algorithms.
Performance evidence is meaningful only when the candidates solve the same problem under the same assumptions.
Use small traces as verification rather than proof. Evaluate the formula at n equal to zero, one and a modest value, then compare it with the pseudocode steps. Boundary cases expose missing iterations and off-by-one counts. If the trace disagrees, repair the count before applying asymptotic rules.
This workflow preserves the distinction among empirical observation, mathematical counting and universal correctness while letting each form of evidence check the others.
What this chapter covers
- 01
Computational problems and algorithms
- 02
Correctness beyond test cases
- 03
Worst-case running-time functions
- 04
Asymptotic upper bounds
- 05
Dominant-term simplification
- 06
Common growth classes
Worked example · free
Count pairwise comparisons
- 2Write the triangular sum.
- 2Convert the sum to a function of n.
- 2State and justify the growth class.
Key terms
- Algorithm
- A finite, well-defined sequence of steps that solves a computational problem.
- Worst Case
- The maximum operation count among inputs of the same size.
- Big-O Bound
- An asymptotic upper bound on growth.
- Invariant
- A property preserved across repeated steps.
Algorithm Design and Growth Rates FAQ
Why do successful tests not prove correctness?
A finite test set covers only selected instances, so an unseen input may still violate the required output. A correctness argument must explain why the algorithm works for every allowed input, often by stating a preserved invariant and showing termination.
When may I drop constants in a running-time function?
After the operation count has been derived and the asymptotic question is clear. Constant multipliers and lower-order terms do not change the growth class, but dropping them before counting can hide a wrong loop range or recurrence.
Is Big-O always a tight description?
No. It is an upper bound, so a linear function is also bounded by a quadratic function. For comparison, choose the slowest-growing standard class that still bounds the function and justify why it is tight.
Exam move
Take one pseudocode fragment each day, annotate the cost of every line and write the sum before using any named complexity class. Then state the invariant that would be needed to prove the same code correct. Build a four-column ledger for input size, basic operation, exact count and tight class. Test the count at n equal to zero, one and four.
Use the identity ∑ from i = 1 to n−1 of i = n(n−1)/2 when a shrinking nested range forms a triangular total. Once a week, compare two correct algorithms for the same contract and explain which term controls growth, which assumptions permit the comparison, and why timing one implementation would not replace the analysis.
Working through Algorithm Design and Growth Rates in COMP5112? Sia is AskSia’s AI Computer Science tutor — ask any COMP5112 Algorithm Design and Growth Rates question and get a clear, step-by-step explanation grounded in how COMP5112 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
