1

The number of comparisons and multiplications for the following algorithm should be:

$$\sum_{i=1}^{n}(n-i)\times 2$$

2 as the amount of operations for multiplication is same as for comparisons.

Question: But the solution I found claims that it's $n\times (n-1)\times 2$, could you pleas state why?

enter image description here

Edit: I found out the solution as follows:

$$\sum_{i=1}^{n-1}(n-i)\times 2$$ $$2\times \sum_{i=1}^{n-1} n-2\times \sum_{i=1}^{n-1}i$$ $$2\times (n)(n-1) -2\times \frac{(n-1)n}{2}$$ $$2\times (n)(n-1)$$

Avv
  • 1,159

1 Answers1

1

The product $a_ia_j$ and the maximum function are evalkuated exactly once per pair $(i.j)$ with $1\le i<j\le n$. Thenre are $n\choose 2$ such pairs, hence $n\choose 2$ multiplications and $n\choose 2$ comparisions (implicit in $\max$) givig a total of $n(n-1)$. (This assumes that we do not count the comparisons of index variable against end expressin that we implicitly have in the for loop).

Hagen von Eitzen
  • 374,180