Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Time Complexity of comparing the elements in the same array to each other only once?

I Know that a nested for loop for the same array is in O(n^2) but was wondering what the complexity of comparing each element of an array to all others in the same array just once? Lets say element A is compared to element B, then when its element B's turn to compare to others it doesn't need to compare to A as that was done in the previous step. So with each iteration the array is getting smaller. Is this still O(n^2)?

Something like this:

for i in xrange(len(list)-1):
    v = list.pop(0)
    for vi in docs:
        merge(v,vi)

Thanks

like image 392
Mo. Avatar asked Mar 27 '14 02:03

Mo.


1 Answers

I always prefer give an answer visually. Nested two for loops for all elements can be thought as a matrix. You will do calculations in number of:

n^2 - n

which resides in O(n^2). Visually, it will be something like (X's represent calculations):

Full Matrix

With your approach, it will become a triangular matrix something like (X's represent calculations):

Triangular Matrix

So you will end up with calculations in amount of:

(n-1) x n/2

As it can be seen, it is half of previous one, but still resides in O(n^2).

like image 139
ismailgulek Avatar answered Oct 10 '22 05:10

ismailgulek