# Introduction

This is a hand-in written by Group 7 (FIRE) for the Algorithms course (TIN092) at Chalmers University of Technology.

Group 7 consists of:

• 901011-0279

• twingoow@gmail.com

• Program: IT

• 920203-0111

• nicale@student.chalmers.se

• Program: IT

# a) Complexity

Our algorithm for calculating a numerical value is, in pseudocode:

Computes the numerical value for C(n) for average quicksort complexity Input: n is the size of the problem. C(n): if n = 0 then: return 1 end if sum <- 0 for i: 0 .. n-1 do: sum <- sum + C(i) end for return 2/n * sum + n end

The complexity of this algorithm in turn is:

\begin{aligned} T(n) = \begin{cases} c_0 & \text{if } n = 0\\ c_1 + \displaystyle\sum_{i = 0}^{n-1} T(i) & \text{if } n > 0 \end{cases}\end{aligned}

$$T(n-1), n > 1$$ is, using the recursive definition above: $T(n-1) = c_1 + \sum_{i = 0}^{n-2} T(i)$

Using this, we expand $$T(n)$$ and get:

\begin{aligned} T(n) &= c_1 + \sum_{i = 0}^{n-2} T(i) + T(n-1)\\ &= 2T(n-1)\end{aligned}

Thus we get:

\begin{aligned} T(n) = \begin{cases} c_0 & \text{if } n = 0\\ 2^{n-1}(c_0 + c_1) & \text{if } n > 0 \end{cases}\end{aligned}

Meaning \(T(n) \in \ma