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**: 2018-01-17, 09:15AM 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 if `n`

is the number of bits
in the input, and in this model we pay `Θ(n)`

cost to add two `n`

bit
integers (and to divide an `n`

bit integer by 2).

```
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). Let `J(A,p,q)`

count the number of
inversions `(i,j)`

with `p ≤ i < j ≤ q`

(it follows that `J(A,0,n-1)=I(A)`

).
Consider the following recursive definition for `J(A,p,q)`

```
J(A,p,q) = J(A,p,⌊(p+q)/2⌋) + J(A,⌊(p+q)/2⌋+1,q) + S(A,p,⌊(p+q)/2⌋,q)
```

where `S(a,b,c)`

counts the number of inversions `(i,j)`

with `a ≤ i ≤ b < j ≤ c`

.

Give a divide and conquer algorithm based on this definition, and
analyse your algorithm. For full credit, the running time should be
`O(n · (log₂ n)²)`

; for extra challenge, try to find a `O(n log₂ n)`

algorithm.

**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.