CS3230 AY 2025/26 Semester 2

Return to main page

Assignment #1 Statistics and Comments (T04)

The average score in our class is 7.4 / 8. Below are the statistics for each question:

General Remarks: Please note that we are looking for formal proofs in your submissions. Intuitions and workings should not be included as part of your submission. For example, for Question 1(b), you should not include more than one base case, or the reason why you "observed the pattern". All we want is just a claim of the answer followed by a formal proof (e.g. proof by induction). Please keep in mind as you prepare your future assignment writeups.
Also, please name your files containing your matric number (that starts with A). My processing scripts need that...

Question 1(a):

  • Some students wrote proofs that are either too long or too short. For this question, since we don't care about the ordering for functions with the same asymptotic growth (if $f(n) = \Theta(g(n))$, either can come first), you only need to show that $f(n) = O(g(n))$ for all adjacent pairs of functions $f(n), g(n)$. This can be done in 1-2 lines for each pair.
    There is no need to show why $g(n) \notin O(f(n))$.
  • For those who proved by definition, note the order of deduction. You should first pick values of $c$ and $n_0$, then prove that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$. DO NOT start by saying $f(n) \leq c \cdot g(n)$. (Note: The order of presenting the proof is not same as your rough work.)
  • Besides, you shall pick constants $c$ and $n_0$ such that it is clear why $f(n) \leq c \cdot g(n)$, even without a calculator.
    For example, when proving $16^n = O(n!)$, it is unclear when $16^n$ starts to grow larger than $n!$. Instead, we can simply set $c = 16^{16}$ so that $16^n = 16^{16} \cdot 16^{n-16} \leq 16^{16} \cdot (n \cdot (n-1) \cdot \cdots \cdot 17) \leq 16^{16} \cdot n!$ for $n \geq 16$.
    Notice that it is very clear in this argument why each inequality sign holds!
  • For those who proved by limit method, please ensure that your limit is derived clearly. Example: Instead of directly saying $\lim_{n \to \infty} \frac{n^2}{n^3 - n^2 \log n} = 0$, you should probably express it as $\lim_{n \to \infty} \frac{1}{\frac{n}{\log n} - 1}$ first. (Then optionally, use L'Hopital's Rule to derive $\lim_{n \to \infty} \frac{n}{\log n} = \lim_{n \to \infty} \frac{1}{\frac{1}{n}} = \infty$.)
    (P.S. In many cases, proving by definition is simpler, e.g. $n! = O(n)$ since $n! \leq n$ for all $n \geq 1$.)
  • There is no reason for you to use both methods to reach the same conclusion.

Q1(b) and Q2 are well done. See the individual comments in the PDF.

Q3:

  • Many students did not get the part $\lceil \log f(n) \rceil \notin o(\lceil \log g(n) \rceil)$ right.
    Firstly, limit method does not apply here -- the statement of limit method only says $\lim_{n \to \infty} \dfrac{f(n)}{g(n)} = 0 \Rightarrow f(n) = o(g(n))$.
    This does NOT give you a way to prove that $f(n) \notin o(g(n))$ (you're assuming the inverse of the statement).
    Some of you also assumed $f(n) = \Theta(g(n)) \Rightarrow f(n) \notin o(g(n))$ without proof.
  • The correct way to do this is to negate the definition (as we did in tutorials).
    Luckily, as we are proving small $o$, we only have to give one constant $c$ such that for all $n_0$, there exists $n > n_0$ such that $\lceil \log f(n) \rceil \geq \lceil \log g(n) \rceil$. This should be relatively straightforward.
Last updated: 26 January 2026