CSE310 HW01 Grading Keys1. (10 pts) Let f(n) = n2and g(n) = 100 × n × log2n. Find the smallest integer N ≥ 0 suchthat f(N) ≤ g(N ) but f(N + 1) > g(N + 1). Show the values of N, f(N), g(N ), f (N + 1)and g(N + 1).Solutions: How to obtain the correct N? You can write a program to iteratively check forN = 1, 2, . . ..N=996, f(N)=992016, g(N)=992016.19, f(N+1)=994009, g(N+1)=993156.Grading Keys:6 pts for the value of N, 1 pt each for f(N), g(N ), f (N + 1), g(N + 1).2. (10 pts) For each function f(n) (the row index in the following table) and time t (the columnindex in the following table), determine the largest size n of a problem that can be solved intime t, assuming that the algorithm takes f (n) microseconds to solve an instance of a problemof size n. Fill the value n in the corresponding entry.1 second 1 minute 1 hour 1 day 1 year√n 10123.6 × 10151.296 × 10197.46496 × 10219.95 × 1026n 1066 × 1073.6 × 1098.64 × 10103.154 × 1013n21037745 6 × 104293938 56160482n19 25 31 36 44How to get those numbers? For the first function, you can easily solve the equation to getthe answer. For the next two functions, you can solve the equation to obtain a real valuednumber. The floor of that real number should work. For the last function, you can try outfor n = 1, 2, . . ..Grading Keys: 0.5 pt per entry.3. (10 pts) Prove that Θ(n) + O(n3) = O(n3).Solution:Let an element of the LHS be f (n) + g(n), where f (n) ∈ Θ(n) and g(n) ∈ O(n3). We need toshow that f(n) + g(n) ∈ O(n3).Since f(n) ∈ Θ(n), we also have f (n) ∈ O(n). Therefore there exists constants c1> 0 andinteger N1such thatf(n) ≤ c1× n, ∀ n ≥ N1. (1)1Since g(n) ∈ O(n3), there exists constants c2> 0 and integer N2such thatg(n) ≤ c2× n3, ∀ n ≥ N2. (2)Let N = max{N1, N2} and c = c1+ c2. Then we havef(n) + g(n) ≤ c × n3, ∀ n ≥ N. (3)This proves that f(n) + g(n) ∈ O(n3).Now let f (n) be an element of the RHS, i.e., f (n) ∈ O(n3). Therefore there exists positiveconstant c1> 0 and integer N1such thatf(n) ≤ c1n, ∀ n3≥ N1.Let g(n) = f(n) − n. Then we haveg(n) ≤ c1n, ∀ n3≥ N1.Therefore g(n) ∈ O(n3). Note that f(n) = n + g(n). This shows that f(n) is also an elementof the LHS. 2Grading Keys: (only grade the direction LHS ∈ RHS4 pts for trying to find an upper bound.2 pt each for the constants for f(n).2 pt each for the constants for g(n).2 pts for correctness.4. (10 pts) Prove that n100= O(2n).Solution: Since limn→∞n1002n= 0, there exists an integer N such thatn1002n≤ 1, ∀ n ≥ N. (4)This impliesn100≤ 2n, ∀ n ≥ N. (5)Therefore n100= O(2n). 2Grading Keys:4 pts for trying to find an upper bound.6 pts for correctness.25. (10 pts) Prove that nn+26= θ((n + 2)n).Solution:Since limn→∞(n+2)nnn= e2, we have limn→∞(n+2)nnn+2= 0. This implies nn+26= θ((n + 2)n). 2Grading Keys:4 pts for trying to use proof by contradiction.6 pts for
View Full Document
Unlocking...