See also the general rules about assignments in this course.

[JE] refers to http://jeffe.cs.illinois.edu/teaching/algorithms/notes/01-recursion.pdf

**DUE**: 2016-09-22, 16:30AM in the assignment box.

## Questions

**1** Prove that the running time of the following algorithm is `Θ(n²)`

[JE1.1]
It's important to note that `n`

is the number of bits in the input.

```
PeasantMultiply(x,y)
while(x>0)
if x is odd:
prod ← prod + y
x ← ⌊ x/2 ⌋
y ← y + y
return prod
```

**2** Counting inversions (related to [JE1.14])

An inversion in an array A[1 .. n] is a pair of indices (i, j) such
that i < j and A[i] > A[ j]. The number of inversions `I(A)`

in an
n-element array `A`

is between 0 (if the array is sorted) and n(n-1)/2
(if the array is sorted backward). Give a recursive function to
compute `I(A)`

by considering the two halves of `A`

.

**3** Use the recursion tree method to solve the recursion relation
T(n) = 49 T(n/25) + O(nᵏ log n) where k=3/2.