Number of actions of array_unique PHP

Question

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

This answer 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
– BoltClock, Commented Nov 29, 2011 at 5:58
A related question/answers: stackoverflow.com/questions/478002/… — Ozair Kafray
– Ozair Kafray, Commented Nov 29, 2011 at 6:00

starrify · Accepted Answer · 2011-11-29 06:00:40Z

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.

edited Nov 29, 2011 at 6:00

answered Nov 29, 2011 at 5:58

starrify

14.9k6 gold badges40 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Lizard Over a year ago

it did google and checked the manual, and only came up with stackoverflow.com/questions/2473989/… which didn't list array_unique

starrify Over a year ago

@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.

Collectives™ on Stack Overflow

Number of actions of array_unique PHP

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related