Question 6: Running Time Analysis Consider the following algorithm: 1: function COUNTPOWERS(n) count 0 for i-1 to n do 3: k i 5 hile k divisible by 2 do 6: 7: 8: 9: end for 10 return count 11: end function k-k/2 count = count + 1 end while (a) Prove that the running time of COUNTPOWERS is O(n log n) b) With more careful analysis, prove that the running time of COUNTPOWERs is O(n) and that this is the tightest bound possible (Hint: You may find the following fact useful: n = n)