# Lab Exercises Week 11

## Complexity

For this week's lab exercises, create a file `Lab11.hs`

. In
this file enter the function definitions appearing in the exercises
below. Then, following the function definitions, in a multi-line
comment, enter the derivation for the timing function and the proof that
the function is in a certain O-class. So,
overall, the structure should be as follows:

foo :: <some type signature>
foo ...<definition of the function>
{- ------------
DERIVATION OF T_...
PROOF:
-}

### Ex 1:

Given the following function definition:

foo:: [Int] -> Int
foo [] = []
foo (x:xs) = (bar xs) + (foo xs)

- Derive the timing function for
`foo` under the
assumetion that T_{bar}(n) = 2 (n is the length of
the input list). Does `foo` have constant, linear or
quadratic work complexity? Justify your answer (which
O-class? Provide witnesses c and n_{0} to the proof)

- Derive the timing function for
`foo` under the
assumetion that T_{bar}(n) = 3 * n + 1 (n is the
length of the input list). Does `foo` have constant,
linear or quadratic work complexity? Justify your answer (which
O-class? Provide witnesses c and n_{0} to the proof
or use the observations discussed in the lecture)

**When you have completed the above exercise show it to your
tutor for this week's core mark.**
### Ex 2:

The following program is yet another definition of
a function that sorts the elements of a list.
Ord a => [a] -> [a]
bubbleSort:: Ord a => [a] -> [a]
bubbleSort xs
| xs == xs' = xs
| otherwise = bubbleSort xs'
where
xs' = bubble xs
bubble (x:y: xs)
| x < y = x : (bubble (y:xs))
| otherwise = y : (bubble (x:xs))
bubble xs = xs

- Assume comparing two lists (
`==`) has constant work
complexity (i.e, n:length of first list, m: length of second
list, T_{==}(n,m) = 1) . What is the asymptotic work
complexity of `bubbleSort` in the worst case
and the best case?

*Hint:* To understand `bubbleSort`, use stepwise
evaluation to
evaluate `bubbleSort [2,1,4,3]` and `bubble
[4,3,2,1]`. How does `bubble` alter the order of
elements in a list? Under which condition is `bubble xs ==
xs`?
**When you have completed the above exercise show it to your
tutor for this week's advanced mark.**

### Additional Exercise

Does the asymptotic work complexity of
`bubbleSort` change if you use the
(more realistic) assumption that

T_{==} (m,n) = min
(m,n)?