Search code examples
phptime-complexitysplbig-o

Time-complexity for Standard PHP Library (SPL) functions

After googling for a bit it seems there's no documentation on the complexity of each of the SPL functions. Has anyone came across with some of information on this aspect?

Solution

  • PHP Architect has a book called Mastering the SPL LIbrary The section on data structures has a table with the code complexity for all data structures for the following operations:

    • Insert elements at the beginning I
    • Insert elements at the end
    • Insert elements in the middle
    • Delete elements from the beginning
    • Delete elements from the end
    • Delete elements from the middle
    • Sequential read
    • Random reads

    You will be surprised how many of these operations are O(1), yet the actual speed can be different because some data structures make better use of memory.

    I definitely suggest getting the book as it has some helpful information.