### Data Structures and Algorithms 2, Fall 1998 Problem Set 1 (9-11 Nov.)

1. Arrange the following functions in an increasing sequence according to their order of growth (big-O) classes:

(The notation `` '' denotes here and in the problems below base-2 logarithms.)

2. Show that

(Hint: Construct an upper bound for the value of the sum using the term, and a lower bound using the term .)

3. Analyze the worst-case complexity of the following ``selection sort'' algorithm:
```
selectsort(  ):

(  )		 		 for    to n-1 do

(  ) 		 		 {   ;   ;

(  ) 		 		 		    for    to n do

(  ) 		 		 		    		 if A[j] <  amin then

(  ) 		 		 		 		 		 {  ;   }

(  ) 		 		 		   ;    }

}

```
4. Solve, by unwinding, the following recurrence equation:

5. Determine the order of growth (big-O) classes for the following recurrence equations. In each case the boundary condition is T(1) = 1, and the functions need to be considered only for values of n that are powers of 2. (Note: Item (d) is slightly more difficult than the others.)
(a)
T(n) = T(n/2) + 1,
(b)
T(n) = 2T(n/2) + n,
(c)
.
(d)
,

6. Analyze the worst-case complexity of the following recursive algorithm for determining the maximum and minimum elements of an array , in the case when n is a power of 2.
```
function   ;

begin

(  )		 		 if n=1 then return (A[1],A[1])

else begin

(  ) 		 		 		   ;

(  )

(  ) 		 		 		 return

end

end   .

```

Pekka Orponen
Tue Nov 3 20:30:43 EET 1998