3. [14 marks] algorithm analysis [3 marks] Prove the claim in Exercise 5.4. The useful formula should be a summation over ir' rather than ix'. . [2 marks] Use precise reasoning to find the average run-time in Exercise 5.4 if the words "1 and 10" [3 marks] Define the input size of counter (below) as n = s+u. Find, and prove, a big-Theta bound . [3 marks] Now, find and prove, a big-Theta bound in terms of n for the best-case run-time of counter. are replaced by "1 and 500." in terms of n for the worst-case run-time of counter Page 2/3 CSC165H1, Fall 2017 Problem Set 4 [3 marks] Based on the previous two questions, what (if anything) can you say about a big-Theta bound on the average run-time of counter? Explain are nat ral numbers