CSE310 HW01 Grading Keys 1 10 pts Let f n n2 and g n 100 n log2 n Find the smallest integer N 0 such that 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 for N 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 column index in the following table determine the largest size n of a problem that can be solved in time t assuming that the algorithm takes f n microseconds to solve an instance of a problem of size n Fill the value n in the corresponding entry n n n2 2n 1 second 1012 106 103 19 1 minute 3 6 1015 6 107 7745 25 1 hour 1 296 1019 3 6 109 6 104 31 1 day 7 46496 1021 8 64 1010 293938 36 1 year 9 95 1026 3 154 1013 5616048 44 How to get those numbers For the first function you can easily solve the equation to get the answer For the next two functions you can solve the equation to obtain a real valued number The floor of that real number should work For the last function you can try out for 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 to show that f n g n O n3 Since f n n we also have f n O n Therefore there exists constants c 1 0 and integer N1 such that f n c1 n n N1 1 1 Since g n O n3 there exists constants c2 0 and integer N2 such that g n c2 n3 n N2 2 Let N max N1 N2 and c c1 c2 Then we have f 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 positive constant c1 0 and integer N1 such that f n c1 n n3 N1 Let g n f n n Then we have g n c1 n n3 N1 Therefore g n O n3 Note that f n n g n This shows that f n is also an element of the LHS 2 Grading Keys only grade the direction LHS RHS 4 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 100 Solution Since limn n2n 0 there exists an integer N such that n100 1 n N 2n 4 n100 2n n N 5 This implies Therefore n100 O 2n Grading Keys 4 pts for trying to find an upper bound 6 pts for correctness 2 2 5 10 pts Prove that nn 2 6 n 2 n Solution n n Since limn n 2 e2 we have limn n 2 0 This implies nn 2 6 n 2 n nn nn 2 Grading Keys 4 pts for trying to use proof by contradiction 6 pts for correctness 3 2
View Full Document
Unlocking...