In class, we learned that log2n=O(np) for any p>0. In the following exercises, we will prove this fact for the special case p1. That is, we will show that log2n=O(np) for any constant p1 using induction. 1. Show that to prove log2n=O(np) for p1, it suffices to show that log2nn for all n1. (Hint: you may use the fact that if p1, then nnp for any n1 ). 2. Now we proceed to showing log2nn for all nN by induction. Show the base case for n=1. 3. Prove the inductive step. That is, show that if log2nn holds for 1nk, then log2(k+1) k+1. (Hint: for k1, compare log2(k+1) and log2(2k) ). Together, parts 1-3 complete the proof that log2n=O(np) for any constant p1. 4. Now prove that for any base b>1 and any p1,logbn=O(np). (Hint: prove that logbn= O(log2n))