PHP built in functions complexity (isAnagramOfPalindrome function) -

i've been googling past 2 hours, , cannot find list of php built in functions time , space complexity. have isanagramofpalindrome problem solve following maximum allowed complexity:

expected worst-case time complexity o(n)  expected worst-case space complexity o(1) (not counting storage required input arguments). 

where n input string length. here simplest solution, don't know if within complexity limits.

class solution {       // function determine if input string can make palindrome rearranging     static public function isanagramofpalindrome($s) {          // here counting how many characters have odd number of occurrences         $odds = count(array_filter(count_chars($s, 1), function($var) {             return($var & 1);         }));         // if string length odd, palindrome have 1 character odd number occurrences         // if string length even, characters should have number of occurrences         return (int)($odds == (strlen($s) & 1));     } }  echo solution :: isanagramofpalindrome($_post['input']); 

anyone have idea find kind of information?

edit

i found out array_filter has o(n) complexity, , count has o(1) complexity. need find info on count_chars, full list convenient future porblems.

edit 2

after research on space , time complexity in general, found out code has o(n) time complexity , o(1) space complexity because:

the count_chars loop n times (full length of input string, giving start complexity of o(n) ). generating array limited maximum number of fields (26 precisely, number of different characters), , applying filter on array, means filter loop 26 times @ most. when pushing input length towards infinity, loop insignificant , seen constant. count applies generated constant array, , besides, insignificant because count function complexity o(1). hence, time complexity of algorithm o(n).

it goes same space complexity. when calculating space complexity, not count input, objects generated in process. these objects 26-elements array , count variable, , both treated constants because size cannot increase on point, not matter how big input is. can algorithm has space complexity of o(1).

anyway, list still valuable not have inside php source code. :)

a probable reason not including information is likely change per release, improvements made / optimizations general case.

php built on c, of functions wrappers around c counterparts, example hypot google search, @ man hypot, in docs math lib http://www.gnu.org/software/libc/manual/html_node/exponents-and-logarithms.html#exponents-and-logarithms

the source provides no better info https://github.com/lattera/glibc/blob/a2f34833b1042d5d8eeb263b4cf4caaea138c4ad/math/w_hypot.c (not official, easy link to)

not mention, glibc, windows have different implementation. there may different big o per os php compiled on

another reason because it confuse developers. developers know choose function "best" big o

a maximum doesnt mean slower

http://www.sorting-algorithms.com/

has visual prop of whats happening functions, ie bubble sort "slow" sort, yet 1 of fastest sorted data. quick sort many use, slow sorted data. big o worst case - php may decide between release should optimize condition , change big o of function , theres no easy way document that.

there partial list here (which guess have seen)

list of big-o php functions

which list of more common php functions.

for particular example....

its easy solve without using built in functions.

example code

function ispalanagram($string) {   $string = str_replace(" ", "", $string);   $len = strlen($string);   $oddcount = $len & 1;   $string = str_split($string);   while ($len > 0 && $oddcount >= 0) {     $current = reset($string);     $replace_count = 0;     foreach($string $key => &$char) {       if ($char === $current){         unset($string[$key]);         $len--;         $replace_count++;         continue;       }     }     $oddcount -= ($replace_count & 1);   }    return ($len - $oddcount) === 0;  } 

using fact there can not more 1 odd count, can return array.

i think mine o(n) time because worst case o(n) far can tell.

test

$a = microtime(true); for($i=1; $i<100000; $i++) {   testmethod("the quick brown fox jumped on lazy dog");   testmethod("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");   testmethod("testest"); }  printf("took %s seconds, %s memory", microtime(true) - $a, memory_get_peak_usage(true)); 

tests run using old hardware way

took 64.125452041626 seconds, 262144 memory 

your way

took 112.96145009995 seconds, 262144 memory 

i'm sure way not quickest way either.

i cant see info either languages other php (java example).

i know lot of post speculating why not there , theres not lot drawing credible sources, hope partially explained why big o isnt listed in documentation page though