COMPSCI320 Chap.1 Asymptotic Analysis and Algorithm Efficiency
Asymptotic Analysis and Algorithm Efficiency
This chapter sets up the vocabulary used for every running time in the course. It states Big-O, Big-Omega and Big-Theta as inequalities with explicit constants, shows how to prove a polynomial bound in both directions, and explains why transformations such as taking logarithms or exponentials do not preserve Big-O.
The Perrin number lecture then compares a naive recursion, a linear loop and a matrix-power method on the same question.
The chapter is built around the first midterm question type: state a definition with its constants, prove a bound from it and argue a tightest class in both directions.
The Perrin case study then shows why the analysis matters, since three correct programs for the same question differ by many orders of magnitude in running time.
What this chapter covers
- 01
Big-O as an upper bound with constants c and n0
- 02
Big-Omega and Big-Theta
- 03
Proving a tight polynomial bound
- 04
Counterexamples to transformed bounds
- 05
Growth rates of n log n, n squared and 2 to the n
- 06
The Perrin numbers and three algorithms
Worked example · free
Prove a Theta bound with explicit constants
- 1For n ≥ 1 the lower-order terms satisfy 9n ≤ 9n² and 3 ≤ 3n².
- 1Adding gives 5n² + 9n + 3 ≤ 17n², so the expression is O(n²) with c = 17 and n0 = 1.
- 1The extra terms are non-negative, so the expression is at least 5n², giving Ω(n²) with c = 5.
- 1Both bounds hold from n = 1, so the expression is Θ(n²).
Key terms
- Big-O Notation
- An upper bound stating that f(n) is at most a constant multiple of g(n) for all sufficiently large n.
- Big-Theta Notation
- A tight bound stating that f(n) is both an upper-bounded and a lower-bounded multiple of g(n).
- Constant Witness
- The pair of constants c and n0 that makes an asymptotic inequality true and so proves it.
- Perrin Number
- A term of the sequence starting 3, 0, 2 in which each value is the sum of the values two and three places earlier.
- Big-Omega Notation
- A lower bound stating that f(n) is at least a positive constant multiple of g(n) for all sufficiently large n.
- Repeated Squaring
- A method that computes a high power with logarithmically many multiplications by squaring intermediate results.
Asymptotic Analysis and Algorithm Efficiency FAQ
Why does a proof of Big-O need the constants written out?
Big-O is defined by the existence of a constant multiplier and a threshold beyond which the inequality holds. Naming them, for example c = 17 and n0 = 1, turns the claim into something a marker can check line by line. A sentence saying the leading term dominates states the intuition but proves nothing about the definition.
Does f = O(g) imply log f = O(log g)?
No. Taking f(n) = 2 and g(n) = 1 gives f = O(g), but log g is zero while log f is a positive constant, so no multiple of log g bounds log f. The exponential version fails too: with f(n) = 2n and g(n) = n, two to the power 2n divided by two to the n grows without limit.
What made the matrix method for Perrin numbers so much faster?
One step of the recurrence is a fixed 3 by 3 matrix applied to the last three values, so the n-th value comes from a matrix power. Repeated squaring computes that power with a logarithmic number of multiplications, whereas the naive recursion repeats subproblems exponentially often and even a simple loop needs linear time.
Is Big-O the same as the worst-case running time?
No. Big-O is a statement about functions, an upper bound up to a constant, and it can describe best, average or worst cases. Worst-case running time is one particular function of the input size. Saying an algorithm is O(n squared) in the worst case means its worst-case running time is bounded above by a constant times n squared.
Exam move
Rewrite each definition from memory with its constants and threshold, then prove two or three polynomial bounds in both directions until the routine takes under five minutes. Keep a short list of false-looking claims with their counterexamples, such as the logarithm and exponential transformations, because a two-line counterexample is the fastest answer to a true or false question.
Finally, explain to yourself in words why each of the three Perrin algorithms has the growth rate it has. A good self-test is to cover the proof, choose a new cubic or a sum with a logarithm, and produce the constants and the class in writing without looking back at the worked example. Time yourself on one full Theta proof per day for a week; the routine should become mechanical before the exam.
Working through Asymptotic Analysis and Algorithm Efficiency in COMPSCI320? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 Asymptotic Analysis and Algorithm Efficiency question and get a clear, step-by-step explanation grounded in how COMPSCI320 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
