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

1. Let T₁(N) = O(¦ (N)) and T₂(N) = O(¦ (N)). Indicate which of the following are true and which are false, and in one sentence state why.
1. T₁(N) + T₂(N) = O(¦ (N))
2. T₁(N) - T₂(N) = o(¦ (N)) (note: "little-oh")
3. T₁(N) / T₂(N) = O(1)
4. T₁(N) = O(T₂(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 if n > 0

T(n) = 0 otherwise

4. a. Given two sorted lists L₁ and L₂, write a procedure to compute L₁ Ç L₂ using only the basic list operations. Your procedure should be in C++/pseudo-code. You do NOT need to provide a running program.