1
$\begingroup$

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})$

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – GoHokies Nov 8 '16 at 19:34
  • $\begingroup$ @GoHokies is right -- it's actually quite simple. It would be useful if you stated which step in particular you're stuck with. $\endgroup$ – Wolfgang Bangerth Nov 8 '16 at 23:59
  • $\begingroup$ @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. $\endgroup$ – Astro Nov 9 '16 at 4:43
0
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.