Lab 4 Warm-Up Exercises
These exercises are provided to give you practice with algorithmic analysis. They will not be submitted or graded, so you may discuss them with your classmates in any amount of detail. However, make sure that you do not discuss Lab 4 material in detail or share anything you intend to turn in for a grade!
Exercises
- Prove the specified complexity bound for each of the functions below. Remember: Big-\(O\) bounds are shown by finding a \(c\) and \(k\) such that, for any \(n \geq k\), \(cg(n) \geq f(n)\). It’s not enough to just write a prosaic explanation. a. \(n^2 + 2n\) is \(O(n^2)\) b. \(\frac{\log n}{8} - 10^{12}\) is \(O(\log n)\) c. \(\frac{1}{n}\) is \(O(1)\) d. \(\sin x\) is \(O(1)\)
- Prove the following claims by induction. (Give the inductive statement \(P(k)\) and then show both \(P(0)\) and \(P(n) \implies P(n+1)\).) a. For all \(k \geq 1\), \(3^k-1\) is even. b. For all \(k \geq 4\), \(2^n \leq n!\).
- The function
initialize, given below in pseudocode, takes as input an array \(A\) of size \(n\) and initializes every element of the array to \(0\). Using induction and loop invariants, prove that theinitializefunction works correctly. (First, give an invariant \(S(k)\); then prove that the invariant is true for all iterations of the loop; finally, conclude that the function is correct using that loop invariant.) - The function
count, given below in pseudocode, takes a non-negative input a value \(n\) and returns that same value. The new value is constructed by increasing an accumulator once for each time the loop iterates. (This is silly, but useful as an exercise.) Using induction and loop invariants, prove that thecountfunction returns the value that it is given if that value is non-negative.