NivaarExam PrepOfficial exam papers ↗

04-BS-16 · May 2013

Question 6 of 12: Algorithm Analysis and Big-O Notation

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

Notes on this paper

National Examination, 04-BS-16 Discrete Mathematics, May 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, induction & recursion Ch.5, counting Ch.6, discrete probability Ch.7, relations Ch.9, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.

Question 6: Algorithm Analysis and Big-O Notation (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: $i\leftarrow n$; while $i\ge1$: $i\leftarrow\lfloor i/2\rfloor$ (one floor-division per pass). $n\ge1$ an integer.

Find. (a) A closed-form count of loop iterations (floor operations). (b)/(c) The definitions of Big-O and Big-Omega, and proofs that $n!=O(n^n)$ and $n!=\Omega(2^n)$.

  1. (a) Trace the halving sequence. Starting from $i=n$, each pass computes $\lfloor i/2\rfloor$; the loop runs until $i$ first becomes $0$ (since $0<1$ stops it). Repeated integer halving of $n$ reaches $0$ after exactly $\lfloor\log_2 n\rfloor+1$ passes (e.g. $n=4$: $4\to2\to1\to0$, 3 passes, and $\lfloor\log_2 4\rfloor+1=2+1=3$ ✓; $n=5$: $5\to2\to1\to0$, 3 passes, $\lfloor\log_2 5\rfloor+1=2+1=3$ ✓). So the floor operation executes $$\boxed{\lfloor\log_2 n\rfloor + 1 \text{ times.}}$$
  2. (b) Definition of Big-O. $f(n)=O(g(n))$ means there exist positive constants $c$ and $n_0$ such that $|f(n)|\le c\,|g(n)|$ for all $n\ge n_0$ — $g$ is an asymptotic upper bound on $f$ up to a constant factor, beyond some threshold.
  3. (b) Prove $n!=O(n^n)$. $n! = 1\cdot2\cdot3\cdots n$ is a product of $n$ factors each $\le n$, so $$n! = 1\cdot2\cdots n \le n\cdot n\cdots n = n^n.$$ Taking $c=1,\ n_0=1$ satisfies the definition, so $\boxed{n!=O(n^n)}$.
  4. (c) Definition of Big-Omega. $f(n)=\Omega(g(n))$ means there exist positive constants $c$ and $n_0$ such that $|f(n)|\ge c\,|g(n)|$ for all $n\ge n_0$ — $g$ is an asymptotic lower bound on $f$ up to a constant factor (equivalently, $g(n)=O(f(n))$).
  5. (c) Prove $n!=\Omega(2^n)$ (i.e. $2^n$ is a lower bound, up to a constant). Claim: $n!\ge2^{n-1}$ for all $n\ge1$, proved by induction. Base $n=1$: $1!=1\ge2^0=1$ ✓. Step: assume $k!\ge2^{k-1}$; then $(k+1)! = (k+1)\cdot k! \ge (k+1)\cdot2^{k-1} \ge 2\cdot2^{k-1}=2^k$ (using $k+1\ge2$ for $k\ge1$). So $n!\ge2^{n-1} = \tfrac12\cdot2^n$ for every $n\ge1$: taking $c=\tfrac12,\ n_0=1$, $$\boxed{n! = \Omega(2^n).}$$
Final results — Question 6
PartResult
(a)$\lfloor\log_2 n\rfloor+1$ floor operations
(b)Definition given; $n!\le n^n\Rightarrow n!=O(n^n)$, $c=1,n_0=1$
(c)$n!\ge2^{n-1}=\tfrac12\cdot2^n \Rightarrow n!=\Omega(2^n)$, $c=\tfrac12,n_0=1$