advertisement

CSE 326 HW 1 Related reading: Chapters 2 & 3 Due date: Friday, April 6, 2001 in class Total points: 40 points + 5 possible extra credit points Homework #1 1. Let T1(N) = O((N)) and T2(N) = O((N)). Indicate which of the following are true and which are false, and in one sentence state why. a. T1(N) + T2(N) = O((N)) b. T1(N) - T2(N) = o((N)) (note: “little-oh”) c. T1(N) / T2(N) = O(1) d. T1(N) = O(T2(N)) 2. a. What is the time complexity of the following code segments? Show the time complexity analysis and indicate your final solution. i. sum = 0; for( i = 0; i< n; i++ ) for( j = 0; j < i; j++) sum++; ii. sum = 0; for( i = 0; i< n; i++ ) for( j = 0; j < i * i; j++) for( k = 0; k < j; k++) sum++; b. Extra Credit: In addition to time complexity, we are often interested in the space requirement of an algorithm. Analyze the space complexity of the above code segments and give your final result in Big-Oh. 3. a. Solve the following recurrence equation. T(n) = b. Compare the recurrence equation below to the equation in part a., which of them is asymptotically larger? T(n) = c. Solve the following recurrence equation. 3T(n/2) + n T(n) = 0 if n > 0 otherwise 4. a. Given two sorted lists L1 and L2, write a procedure to compute L1 L2 using only the basic list operations. Your procedure should be in C++/pseudo-code. You do NOT need to provide a running program. b. What is the time complexity of your algorithm?