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

Group 7 consists of:

**Mazdak Farrokhzad**901011-0279

twingoow@gmail.com

Program: IT

**Niclas Alexandersson**920203-0111

nicale@student.chalmers.se

Program: IT

We first try to develop a naïve algorithm that doesn’t use dynamic programming. The algorithm uses exhaustive search by going through the companies one at a time, and for each amount invested in that company, comparing the result of investing a little bit more in the company with the result of not investing any more and moving on to the next company. For this, we introduce another variable \(a\), to keep tack of the amount currently invested in company \(i\).

```
function maxReturn(i, x) begin
return mr(i, x, 0)
end
function mr(i, x, a) begin
if i = 0 then
return 0
end
if x = 0 then
return 0
end
return max(g(i, a + 1) + mr(i, x - 1, a + 1), g(i, a) + mr(i - 1, x, 0))
end
```

[H]

[1]

The time complexity function can be expressed as the recursive function:

\[\begin{aligned} T(i, x) = \begin{cases} c_0 & \text{if $i = 0$}\\ c_1 & \text{if $x = 0$}\\ c_3 + T(i, x-1) + T(i-1, x) & \text{if $i \neq 0 \land x \neq 0$} \end{cases}\end{aligned}\]

Since the value of \(a\) only affects the return value and not the time complexity, we do not include it as a parameter to the complexity function.

Which when substituting \(i + x\) for \(p\) gives us:

\[\begin{aligned} T(p) &= c_3 + 2T(p-1)\\ &= 2^p + \sum_{i=0}^{p} \left[ c 2^i \right]\\ &= 2^p + c\left[ \frac{1-2^p}{1-p} + 2^p \right]\\ &= (1 + c)2^p + c\frac{1-2^p}{1-p}\\ &\in \mathcal{O}(2^p)\end{aligned}\]

## Share on Social Media