04-BS-16, December 2014, Q12 | Nivaar Exam Prep

Question 12

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a1) $f(n)=5n^2+3n\log_2n$. (a2) $f(n)=2+4+6+\cdots+2n$. (b) The integers $1369$ and $2597$.

Find. (a) The tightest simple Big-O bound for each function. (b) $\gcd(1369,2597)$, and integers $a,b$ with $\gcd=1369a+2597b$ (Bezout's identity).

Approach. Compare growth rates term-by-term for (a) (a lower-order log factor never changes the Big-O class set by the dominant polynomial term); run the Euclidean algorithm forward for the gcd, then back-substitute (extended Euclidean algorithm) for the Bezout coefficients.

a1) Bound $5n^2+3n\log_2n$. Since $\log_2n\le n$ for all $n\ge1$, we have $3n\log_2n\le3n^2$, so $f(n)\le5n^2+3n^2=8n^2$ for all $n\ge1$ — a valid Big-O witness with $C=8,k=1$. The $n^2$ term dominates the smaller-order $n\log n$ term, and no lower power of $n$ bounds $f$ (the $5n^2$ term alone already grows like $n^2$). $\boxed{f(n)=O(n^2)}$.
a2) Bound $2+4+\cdots+2n$. This is $2(1+2+\cdots+n)=2\cdot\frac{n(n+1)}{2}=n(n+1)=n^2+n$. Since $n^2+n\le2n^2$ for all $n\ge1$, $C=2,k=1$ is a valid witness. $\boxed{f(n)=n^2+n=O(n^2)}$.

b) Run the Euclidean algorithm forward. Repeatedly divide-and-remainder, larger by smaller:

Euclidean algorithm on 1369, 2597
Step	Division	Quotient $q$	Remainder $r$
1	$2597 = 1\cdot1369 + 1228$	1	1228
2	$1369 = 1\cdot1228 + 141$	1	141
3	$1228 = 8\cdot141 + 100$	8	100
4	$141 = 1\cdot100 + 41$	1	41
5	$100 = 2\cdot41 + 18$	2	18
6	$41 = 2\cdot18 + 5$	2	5
7	$18 = 3\cdot5 + 3$	3	3
8	$5 = 1\cdot3 + 2$	1	2
9	$3 = 1\cdot2 + 1$	1	1
10	$2 = 2\cdot1 + 0$	2	0

The last nonzero remainder is $1$, so $\boxed{\gcd(1369,2597)=1}$.

b) Back-substitute to find $a,b$ (extended Euclidean algorithm). Running the coefficient recurrence $(s,t)$ forward alongside the same divisions (each new remainder's coefficients $=$ previous pair's minus $q\times$ current pair's) yields, at the final step where the remainder reaches $1$: $$1 = (-1013)\times1369 + 534\times2597$$ Direct check: $(-1013)(1369)=-1{,}386{,}797$ and $(534)(2597)=1{,}386{,}798$, summing to $1$. $\boxed{\gcd(1369,2597)=1=(-1013)(1369)+(534)(2597)}$, i.e. $a=-1013,\ b=534$ (Bezout coefficients; not unique — any $a+2597k,\ b-1369k$ for integer $k$ also works).

Question 12 results
Part	Result
a1	$O(n^2)$
a2	$O(n^2)$ (exactly $n^2+n$)
b	$\gcd(1369,2597)=1=(-1013)(1369)+(534)(2597)$

Topic: Big-O (asymptotic) notation; the Euclidean and extended Euclidean algorithms.

Key relations: $\log_2n=O(n)$, so any $n\cdot\log n$ term is absorbed into $O(n^2)$ once multiplied by $n$; the Euclidean algorithm's last nonzero remainder is $\gcd$; back-substitution (or the linear recurrence on coefficient pairs) produces Bezout's identity $\gcd(a,b)=sa+tb$.

Why this works: Big-O cares only about the dominant term's growth rate, so any strictly-lower-order additive term (like $n\log n$ next to $n^2$) can always be absorbed into a larger constant multiplying the dominant term; the Euclidean algorithm terminates because remainders form a strictly decreasing sequence of non-negative integers, and gcd is preserved at every division step ($\gcd(a,b)=\gcd(b,a\bmod b)$).

Common pitfall: Reporting a "tighter-looking" but incorrect bound like $O(n\log n)$ for (a1) by focusing on the wrong term — always compare ALL terms' growth rates, not just the one that looks unusual; for (b), sign errors accumulate quickly in the back-substitution and should always be checked by direct multiplication at the end.

Source: Rosen, Discrete Mathematics and Its Applications, 7th ed., Ch. 3.2 (Growth of Functions), Ch. 4.3 (Euclidean Algorithm, Bezout's Theorem).

Question 12 of 12

Question 12