Data Structures

.(5 pts) An algorithm takes 1 ms for input size 100. How long will it take for input size 800 if the running time is the following (assume low-order terms are negligible): o Linear the logarithm to the base 2 o Quadratic o Cubic (5 pts) Use the definition of Big-Oh to prove that if f(n) is O(g(n)), then af(n) is O(g(n)), for any positive constant a. .(7 pts) What is the asymptotic complexity of the following functions? Justify your answer. i Assume that the function Combine runs in O(n) time when |left-rightl n, i.e., when Combine is used to combine n elements in the array a. void DoStuff^int all, iat leftiat right) // poatsondition: a[left]