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) Function

Naïve function

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 

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}