-2

I have an array, and I want to compare elements between each other, but want to avoid comparing them more than once, so in other words, once I compare array[0] with array[1], I don't want to compare again array[1] with array[0], I will end up having this code:

for(var i:int = 0; i < array.lenght; i++){

     var entity:Object = array[i];

      for(var j:int = i; j < array.lenght; j++){

          //do stuff

      }

  }

This is not O(N^2), maybe it is O(logN)?. What method do you use to calculate this?.

Artemix
  • 8,497
  • 14
  • 48
  • 75

2 Answers2

4

You have to count the times the inner block would be executed:

for array length n, where n =

3 => 2 + 1 = 3
4 => 3 + 2 + 1 = 6
5 => 4 + 3 + 2 + 1 = 10
6 => 5 + 4 + 3 + 2 + 1 = 15

So for the array of length n the number of times it will execute the inner block (with comparison or whatever) is a sum of all integers less than n. In fact there is a well known formula to sum all integers less then n:

(n - 1) * n / 2

let's expand it to the following:

1/2 * (n^2 - n)

so, speaking in big-o terms:

  1. you could ignore the -n because it gives a relatively small change when n is big (like if n = 1000, then n ^ 2 is 1000000, so -n is just 0.1% of n ^ 2, and the bigger the n the less it affects). that leads us to the following:

    1/2 * (n ^ 2)

  2. the constant is traditionally ignored in a big-o notation (because it doesn't affect the growth rate, which we need to measure), so now we have just n ^ 2

so the answer is O(n^2)

leetwinski
  • 17,408
  • 2
  • 18
  • 42
  • It shouldn't be n^2, it is at some place in between n and n^2. – Artemix Oct 09 '15 at 21:35
  • 1
    Well that is the way it works: in big-o notation you don't measure how many times the instruction would be executed exactly, but how fast will this amount grow with the increase of n. When n is small this differences seem to be significant, but you don't have to care about the small n. so for big n `1/2 * (n^2 - n) ~ n^2`. It is the measure of how good (or bad) algorithm is for big inputs. – leetwinski Oct 09 '15 at 21:39
  • once again: when `n = 10000`: `1/2(n^2 - n) = 4999950000`, and `1/2 * n^2 = 5000000000`. So the difference makes just 0.001%. for n = 1M this percentage is even less. so ok, it is between n and n^2, but MUCH-MUCH closer to n^2 – leetwinski Oct 09 '15 at 21:58
  • A well constructed answer. – BadFeelingAboutThis Oct 09 '15 at 23:12
-2

It's a matter of index in that case. You pick the element and compare not against the entire array but against the array starting at the element index + 1. For example (pseudo code):

var index:int = 0;
while(index < array.length - 2)//no need to run for last element
{
    var element:* = array[index];
    for(var i:int = index + 1; i < array.length; i++)
    {
        //compare element with array[i]
    }            
    index++;
}

the first iteration will run through the array - one element but then on the next loop it will go through the array - 2, etc until it reaches the second last element after which it quits.

BotMaster
  • 2,233
  • 1
  • 13
  • 16