- Below are 12 functions of
*n*(recall that lg (ln) denotes the binary (natural) logarithm):

1*.*3 *n*2 2*n n*√*n n*p√*n n*lg(*n*)*n*ln(*n*)(1*.*001)*n n**n n*! *n*lg(*n*)2*n*+7

*n*

Arrange these functions in non-decreasing order of growth; that is, find an arrangement *f*_{1 }≤ *f*_{2 }≤ *… *≤ *f*_{12 }of the functions such that *f*_{1 }∈ *O*(*f*_{2}), *f*_{2 }∈ *O*(*f*_{3}), …*f*_{11 }∈ *O*(*f*_{12}). For each *i*, you should write *f _{i }*≡

*f*

_{i}_{+1 }if

*f*∈ Θ(

_{i }*f*

_{i}_{+1}), but

*f*

_{i }< f_{i}_{+1 }otherwise. You do not need to argue for your answers.

- In this exercise we shall employ two data structures:

- a
*queue*, with three operations:- IsEmpty?() which returns true iff (if and only if) the queue is empty.
- InsertLast(
*x*) which inserts*x*at the end of the queue. - RemoveFirst() which returns the queue’s first element (which is removed from the queue).
- a
*priority queue*, with three operations: - IsEmpty?() which returns true iff the priority queue is empty.
- Insert(
*x*) which inserts*x*into the priority queue. - RemoveMax() which returns (and removes) the priority queue’s
*largest*

The program below takes as input a queue *Q *and then sorts it (in reverse order), using a priority queue *P *which we assume is initially empty.

Sort(*Q*) **while **not Q.IsEmpty?() x ← Q.RemoveFirst()

P.Insert(x) **while **not P.IsEmpty?()

x ← P.RemoveMax()

Q.InsertLast(x) **return **Q

We shall assume that each operation on *queues *executes in time Θ(1), i.e., constant time (this can be accomplished by a pointer implementation). We shall also assume that priority queues are implemented such that IsEmpty? executes in time Θ(1), whereas Insert and RemoveMax executes in time Θ(lg*k*) where *k *is the current size of the priority queue (this can be accomplished by a “heap” implementation, as we shall see later in this course).

Let *T*(*n*) be the (worst-case) running time of Sort, given a queue with *n *elements.

- Express
*T*(*n*) as the sum of two summations (each of the form). You do not need to argue

for your answer.

- Use (1) to find a function
*f*, as simple as possible, such that the*T*(*n*) ∈ Θ(*f*(*n*)). You should justify your answer, for example by referring to Theorem 3.28 in*Howell*.

- Estimate the running times, in terms of
*n*, of the following three programs. You should give tight bounds, of the form Θ(*f*(*n*)) with*f*as simplified as possible. Justify your answers; this will involve expressing each running time as a sum. (You can assume that arithmetic operations take time in Θ(1), no matter the size of the operands. Recall that the scope of language constructs is determined by indentation, so in (c),*k*←*k*∗ 2 is part of the while loop but not of the for )

*(a) (b) (c)*

*z *← 0 *z *← 0 *z *← 0

**for ***k *← 1 **to ***n *∗ *n ***for ***k *← 1 **to ***n *∗ *n k *← 1

*q *← 1 *q *← 1 **while ***k < n*

**while ***q *≤ *k s *← *k *∗ *k ***for ***q *← 1 **to ***k*

*q *← *q *+ 1 **while ***q *≤ *s z *← *z *+ 1

*z *← *z *+ 1 *q *← *q *∗ 2 *k *← *k *∗ 2

*z *← *z *+ 1

## Reviews

There are no reviews yet.