Big-O Complexity of Gini Index

What will be the complexity of finding Gini Index of a sorted vector of $N$ values, which is defined as:

$Gini(\mathbf{x})=1-2\sum_{k=1}^N \frac{\mathbf{x}(k)}{\Vert\mathbf{x}\Vert_1}(\frac{N-k+.5}{N})$

• if you mean the computational complexity in terms of $N$, then it's useful to consider (1) how expensive it is to compute $||x||_1$, and how many times you need to do so, and (2) how many operations are need to compute each term in the sum. – GoHokies Nov 8 '16 at 19:34
• @GoHokies is right -- it's actually quite simple. It would be useful if you stated which step in particular you're stuck with. – Wolfgang Bangerth Nov 8 '16 at 23:59
• @GoHokies Here is what i think: Outer summation is like a loop, so we are doing mathematical constant time operations $N$ times. $\Vert.\Vert_1$ is computed only once which is linear in time. Hence overall complexity is $\mathcal{O}(N)$. Please correct if I am wrong. – Astro Nov 9 '16 at 4:43

Even though the biggest part of the question has been answered in the comments, I want to point out a detail that is very important in my opinion.

There are several questions about the complexity you can ask:

• what is the "minimum/tight" asymptotic complexity to find a certain quantity (in your case, it is the Gini index)?
• what is the asymptotic complexity of a certain algorithm (or even its implementation if we want to be very fine-grained)?

Regarding a difference between tight ($\Theta(N)$) and upper bound ($\mathcal O(N))$ complexities, the following question on SO can be useful. I will be using $\Theta$ notation for this answer; though, using $\mathcal O$ is sufficient as well.

Now, for the Gini index, let's consider two "algorithms" to find the desired quantity: variant $A$: that will be described exactly by the formula in your question and variant $B$ described by the modified formula:

$$\text{Gini}_A(\mathbf{x}) = 1-2\sum_{k=1}^{N}\frac{\mathbf{x}(k)}{\color{red}{||\mathbf{x}||_1}}\frac{N-k+0.5}{N}\\ \text{Gini}_B(\mathbf{x}) = 1-\frac{2}{\color{red}{||\mathbf{x}||_1}}\sum_{k=1}^{N}\mathbf{x}(k)\frac{N-k+0.5}{N}$$

Notice, that in algorithm $B$ I explicitly moved the calculation of the vector norm $||\mathbf{x}||_1$ outside of the summation to signal that its computation happens only once. Now, if we assume that algorithm $A$ actually computes the norm $||\mathbf{x}||_1$ $N$ times (for no reason), then:

• the complexity of algorithm $A$ is $\Theta(N^2).$ The calculation of the norm happens $N$ times, and one norm calculation is $\Theta(N)$ complexity.
• the complexity of algorithm $B$ is $\Theta(N)$. First the norm is calculated in $\Theta(N)$, followed by computation of the sum that touches every element of $\mathbf{x}$ once - another $\Theta(N)$ and $\Theta(1)$ multiplication and subtraction.