I need to calculate an average time complexity. I can assume that random's return value is uniformly distributed.
Line 6 has $2$ multiplications, line 8 has $1$ multiplication.
$$T_{avg}(n) = ??$$
The propability that condition in line 5 is satisfied is: $p(n) = \frac{n-1}{n^2} \quad \land n > 1$. Here is quick pseudo-proof:
For $n = 2$ two random function calls will return one of these: $11, 12, 21, 22$ so in total $2^2$ results. Only $11$ is valid one because only that satisfies x1 + x2 = n condition. So $\frac{1}{4} = \frac{n-1}{n^2}$
For $n = 3$ two random function calls will return one of these: $11, 12, 13, 21, 22, 23, 31, 32, 33$ so in total $3^2$ results. Only $12, 21$ are valid. So $\frac{2}{9} = \frac{n-1}{n^2}$.
I know that my proof is not perfect, but it works, improving that proof is not relevant for me.
So the propability of executing 6th line is $p_{if}(n) = \frac{n-1}{n^2}$. Therefore propability of executing 8th line is $p_{else}(n) = 1 – p_{if}(n) = 1 – \frac{n-1}{n^2}$.
$$T_{avg}(n) = \underbrace{\sum_{k = 1}^{n}\frac{n-1}{n^2}2}_{\text{instruction 6}} + \overbrace{\sum_{k=1}^{n}\Bigg(\Big( 1 – \frac{n-1}{n^2}\Big)1\Bigg)}^{\text{instruction 8}}$$
I think I can continue from here. Just not sure if my calculations are correct.
Thanks.
Best Answer
There are $n-1$ chances to obtain the sum $n$ (by $1+(n-1),2+(n-2),\cdots(n-1)+1$) on a total of $n^2$.
Hence the average number of multiplications is
$$1+\frac{n-1}{n^2}.$$
If the generator wasn't uniform, the value would be
$$1+\sum_{k=1}^{n-1}p_kp_{n-k}.$$