You, Alice and Bob are engineering a solution the Really Hard Problem and have come up with ten algorithmic solutions. A

[answerhappygod]

You Alice And Bob Are Engineering A Solution The Really Hard Problem And Have Come Up With Ten Algorithmic Solutions A 1 (135.24 KiB) Viewed 55 times

You, Alice and Bob are engineering a solution the Really Hard Problem and have come up with ten algorithmic solutions. Alice has analysed the code and expressed the run times of the ten solutions with the following ten functions: fo(n)= (3n+3)³ ● fi(n) = Σ=12 • f2(n)= n². (22 n +75) log₂ n • f3(n) = 3¹og₂ n • f₁(n) = (4n² +25). (n²-2n+1) • f5(n) = log₂ (nr³) ● fe(n) = log₂ (n² +5n-3) • f7(n) = log₂ (log₂ n+3) • f8 (n) = 2/ • f9(n) = 22²² a) Alice has asked you to help her classify these functions based on their asymptotic growth rate. That is, she wants you to prove a tight big-Theta bound for each function by following these steps. i. Use algebra to simply the function for ease of analysis. Remember the goal of simplification is to isolate terms and identify the dominant term. For instance, we might want to expand (n + 1)² to n² +2n+ 1 to see that n² is the dominant term. ii. Use your intuition, the limit test, or algebra to come up with a good guess of a tight bound. For instance, after isolating n² as the dominant term we might guess our polynomial is in (n²). iii. Use the limit test or the definitions to prove that your guess is correct. Both methods can provide correct proofs, and its a good idea to practice both methods. Sometimes our guess is incorrect and we need to return to the previous step. b) Now Alice asks you to place the functions in order of asymptotic growth from the slowest growing to the fastest growing. (Remember an algorithm with a fast growing run time function is a slow algorithm and vice versa. It is easy to confuse these when classifying functions.) You do not need to provide proofs in this step, but you may want to use the limit test or algebra to compare your functions. c) Bob has determined that for the instances of the Really Hard Problem that you want to solve the input size is guaranteed to be at most n = 65536. Place the functions from smallest to largest when evaluated at this maximum input size.