04-BS-16 · December 2013

Question 8 of 12: Algorithm Analysis, Big-O, and Growth-Rate Ordering

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Examination, 04-BS-16 Discrete Mathematics, Dec 2013. Closed book, no aids, 3 hours, 12 questions of 10 marks each (100 marks); the exam instructs "answer 10 of 12" but every question is solved below as a complete study resource.

Reference texts: Rosen, Discrete Mathematics and Its Applications, 7th ed. (logic Ch.1, sets Ch.2, induction & pigeonhole Ch.5-6, relations Ch.9, counting Ch.6, discrete probability Ch.7, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.

Question 8: Algorithm Analysis, Big-O, and Growth-Rate Ordering (10 marks)

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. Loop: $y\leftarrow x$; while $y\ge2$: $y\leftarrow\sqrt y$ (one sqrt call per pass), $x\ge0$ real.

Find. (a) A closed-form iteration count. (b) The Big-O definition. (c) The correct growth-rate ordering.

(a) Model repeated square-rooting. After $k$ passes, $y=x^{1/2^k}$. The loop keeps executing while $y\ge2$, so the number of passes $n$ is the smallest integer with $x^{1/2^n}<2$: $$x^{1/2^n}<2 \iff \frac{\log_2x}{2^n}<1 \iff \log_2x<2^n \iff n>\log_2(\log_2x).$$ Checking $x=16$: $\log_2(\log_2 16)=\log_2 4=2$, so $n=\lfloor2\rfloor+1=3$ — trace: $16\to4\to2\to1.41$ (stop), 3 sqrt calls ✓. So for $x\ge2$: $$\boxed{n(x)=\lfloor\log_2(\log_2 x)\rfloor+1}\quad(\text{and }n(x)=0\text{ for }0\le x<2,\text{ loop never enters}).$$
(b) Definition of Big-O. $f(n)=O(g(n))$ means $\exists$ positive constants $c,n_0$ such that $\boxed{0\le f(n)\le c\,g(n)\ \text{for all}\ n\ge n_0}$ — $g$ is an asymptotic upper bound on $f$ up to a constant factor, beyond some threshold.
(c) Order the eight functions. Group by type: iterated-log $\prec$ log $\prec$ polylog $\prec$ polynomial (fractional then integer power) $\prec$ exponential $\prec$ factorial/super-exponential. Applying this hierarchy to the given list: $$\boxed{\log\log n \;\prec\; \log n \;\prec\; (\log n)^2 \;\prec\; \sqrt n \;\prec\; n\log n \;\prec\; n^3 \;\prec\; 2^n \;\prec\; n^n.}$$

Final results — Question 8
Part	Result
(a)	$n(x)=\lfloor\log_2(\log_2x)\rfloor+1$ for $x\ge2$; $0$ for $x<2$
(b)	$\exists c,n_0>0: 0\le f(n)\le cg(n)\ \forall n\ge n_0$
(c)	$\log\log n\prec\log n\prec(\log n)^2\prec\sqrt n\prec n\log n\prec n^3\prec2^n\prec n^n$

Topic: Iterated function analysis (repeated square-rooting) and the standard hierarchy of growth rates.

Key relations: Each square root halves $\log_2 y$, i.e. lowers $\log_2\log_2 y$ by exactly 1 per pass (compare repeated halving, which lowers $\log_2 y$ by 1 per pass — one extra layer of log here); standard growth hierarchy: $O(1)\prec\log\log n\prec\log n\prec n^\epsilon\prec n\prec n\log n\prec n^k\prec c^n\prec n^n\prec n!$.

Why this works: Taking $\log_2$ twice turns "$x^{1/2^n}<2$" into a simple linear inequality in $n$ ($2^n>\log_2 x$), because square-rooting is itself an exponent-halving operation and a second log linearizes the resulting exponential-in-$n$ relationship.

Common pitfall: Off-by-one on the floor/ceiling boundary (verify with a concrete trace like $x=16$, not just the algebra); placing $(\log n)^2$ after $\sqrt n$ instead of before it — any power of $\log n$ is asymptotically slower than any positive power of $n$.

Source: Rosen, Discrete Mathematics and Its Applications, §3.2 (growth of functions, Big-O), §3.1 (algorithm complexity).

← Question 7 Next: Question 9 →