Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/discrete-mathematics-continuous-mathematics-and-probability-resit/2/b/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2022 Discrete mathematics, continuous mathematics and probability resit 2 b Solution by
Codex 0 2026-10-25
Suppose first that . Choose and so that for . There are only finitely many natural numbers below . Because at each of them, all ratios in this finite prefix are finite. LetThen both in the prefix and in the tail, hence on the entire domain of a function. This proves the finite-prefix extension of a big O bound.
Conversely, a bound valid for every natural number is certainly valid eventually. The purported real constant cannot be negative because never vanishes; if it is zero, enlarge it to a positive constant. The definition of Big O notation then applies. The nonvanishing assumption is what permits the finite exceptions to be absorbed into one constant.
New to topics? Read the docs here!