辅导Algorithms、data留学生讲解、辅导Java、Python，c++程序语言
辅导留学生 Statistics统计、回归、迭代|讲解Ja
Quiz #7: Analysis of Algorithms/Complexity Classes ICS-33 Spring 2020
When working on this quiz, recall the rules stated on the Academic Integrity statement that you signed.
Submit your completed written quiz on Gradescope by Friday May 29th at 11:30pm (in the Irvine time zone). I
will post my solutions to Piazza reachable via the Solutions link on Saturday morning.
1. (3 pts) Sketch approximate Size vs. Time curves for the two algorithmic complexity classes required in each of the pictures
below: for one, write Impossible instead: (a) an O(N) algorithm that is alwaysfaster than an O(N2
) algorithm.. (b) an O(N)
algorithm that is never faster than an O(N2
) algorithm. (c) an O(N) algorithm that is sometimesfaster than an O(N2
) algorithm.
2. (2 pts) Assume that a function s is in the complexity class O(𝑵𝑵√𝑵𝑵). (a) What is its doubling-signature:
how much more time (by what factor) does it take to solve a problem twice as large? Show your
calculation and simplification to a numerical answer. (b) Briefly explain why it makes little sense for an
algorithm to be in the complexity class O(1/n)?
3. (6 pts) Assume that functions f1 and f2 compute the same result by processing the same argument. Empirically we
find that Tf1(N) = 10 N log2 N and Tf2(N) = 90N where the times are in seconds. (a) Solve algebraically for what size N
these two functions would take the same amount of time, showing how you calculated your answer. (b) for what size
arguments is it better to use f1? f2? (c) Briefly describe how we can write a simple function f that runs as fast as the
fastest of f1 and f2 for all size inputs. (d) What exact integer value N (±1) solves 𝟐𝟐𝟐𝟐√𝑵𝑵 = 10 (Log2 N2
)+1000?
Use a calculator, spreadsheet, or a program to guess and refine your answer (try plotting values to see where
the curves meet). Your answer should be correct for all digits up to the ones-place: e.g., a number like 23,728.
(d2) Based on your calculation, which complexity class 𝑶𝑶(√𝑵𝑵) or O( (Log2 N2)) grows more slowly; why?
4. (6 pts) The following functions each determine all pairs of two values in alist that sum to asum. As is shown
in the notes, (a) write the complexity class of each statement on its right, where N is len(alist).
def how_sum_1 (alist,asum): def how_sum_2 (alist,asum):
pairs = [] ____ pairs = [] ____
for f in alist: ____ aset = set(alist) ____
for s in alist: ____ for v in alist: ____
if f+s == asum: ____ if asum-v in asset: ____
pairs.append((f,s)) ____ pairs.append((v,asum-v)) ____
return pairs ____ return pairs ____
(b) Write the full calculation that computes the complexity class for the entire function. (c) Simplify what you
wrote in (b).
5. (5 pts) Assume that function f is in the complexity class O(N (log2 N2
)), and that for N = 1,000 the program
runs in 10 seconds.
(a) Write a formula, T(N) that computes the approximate time that it takes to run f for any input of size N.
Show your work/calculations by hand, approximating logarithms, then finish/simplify all the arithmetic.
(b) Compute how long it will take to run when N = 1,000,000 (which is also written 106
). Show your
work/calculations by hand, approximating logarithms, finish/simplify all the arithmetic.
6. (3 pts) Assume that we have recorded the following data when timing three methods (measured in
milliseconds). Based on these times (which are measured and therefore approximate, so don’t expect perfect
results), fill in an estimate for the complexity class (one of the standard ones) for each method and fill in an
estimate for the running time when N = 1,600.
N Time: Method 1 Time: Method 2 Time: Method 3
100 300 20 20
200 604 76 22
400 1,196 325 20
800 2,395 1,178 19
1,600
Complexity
Class Estimate