3

Does anyone know the Big O of array_unique()?

I haven't gone through the source, but I would imagine it loops through each value and checks to to see if it is in the array which would be O(n^2) is this correct?

Thanks

Madara's Ghost
  • 172,118
  • 50
  • 264
  • 308
Lizard
  • 43,732
  • 39
  • 106
  • 167
  • [This answer](http://stackoverflow.com/a/478182/106224) sums it up in steps, but I'm not very inclined to mark your question as a duplicate of that one since it's asking something entirely different :) – BoltClock Nov 29 '11 at 05:58
  • A related question/answers: http://stackoverflow.com/questions/478002/php-arrays-remove-duplicates-time-complexity – Ozair Kafray Nov 29 '11 at 06:00

1 Answers1

3

It's O(nlogn) since it uses sorting instead of your O(n^2) scanning.

Note that keys are preserved. array_unique() sorts the values treated as string at first, then will keep the first key encountered for every value, and ignore all following keys. It does not mean that the key of the first related value from the unsorted array will be kept.

Quoted from http://php.net/manual/en/function.array-unique.php

EDIT: Remember to Google it, check the manual, check for existing questions, and then ask it.

starrify
  • 14,307
  • 5
  • 33
  • 50
  • it did google and checked the manual, and only came up with http://stackoverflow.com/questions/2473989/list-of-big-o-for-php-functions which didn't list array_unique – Lizard Nov 29 '11 at 06:03
  • @Lizard I was going to check if `array_unique` uses sorting, and googled `array_unique sort` as its keyword. Then the 1st result is what I wanted :-) Since it sorts the array and then does a linear scanning, the time complexity would be `O(nlogn)` which is the sorting cost. – starrify Nov 29 '11 at 06:07