Exercise 1: asymptotic behavior (20 points) 1. (10 points) Assume you have two computers, CA and CB, capable of performing 106 and 10 oper- ations per second, respectively. Both computers run a set of algorithms whose precise complexities f(n) are given below. Determine the size n* of the biggest input that can be processed in 1 second for each computer, as in the example f(n) n for CAn for CB lg lg n Vn 14n +4 n log3 n +n 12 10 1016 10 rl 371 The precise complexity tells you how many operations are performed to solve an instance of size n. Assume each operation takes the same time and that the input sizes are natural numbers 1,2,3, 2" (10 points) Prove formally that f(n) = an2 +bn + c where a > 0 is (n2). Hint: find values for the constants c, , no in the definition of (-) and show it holds