# expressing the speed of a sorting algorithm

How would I express the speed of the following sort algorithm? I know bubblesort is n^n (er, I mean n^2...as someone pointed out below). In the following the array decreases each time you call it recursively.

thanks.

``````\$myarray = array("21","4","8","8","1","2","19","21");
mysort(\$myarray);

function mysort(\$myarray,\$sorted = null){
if(!isset(\$sorted)){
\$sorted = array();
}
\$lowest = \$myarray;
\$lowindex = 0;
for(\$x = 1;\$x < count(\$myarray);\$x++){
if(\$myarray[\$x] < \$lowest){
\$lowest = \$myarray[\$x];
\$lowindex = \$x;
}
}
\$sorted[] = \$lowest;
array_splice(\$myarray,\$lowindex,1);
if(count(\$myarray) > 1){
echo "calling recursively \n";
mysort(\$myarray,\$sorted);
}
else if(count(\$myarray) == 1){
\$sorted[] = \$myarray;
\$arraystr = print_r(\$sorted,true);
echo "sorting finished. Array is \$arraystr \n";
return;
}
}
``````
• Nothing about bubblesort is n^n. Bubblesort only needs n^2 comparisons. n^n is nonsense because there are only n! permutations; even the naive brute-force "check every permutation, stop when one is sorted) only takes n * n! comparisons.
– user7043
Jan 25 '14 at 13:20
• Yikes! You are absolutely right. Still, I'm wondering how the speed of the above would be represented. I guess the call to array_splice would have to be taken into consideration. Jan 25 '14 at 13:28
• @lamphp You mention that you're wondering how to express the speed of the algorithm. I know folks have done a good job of explaining how fast it is, but I guess I wanted to answer the general question a bit. Usually when you look at an algorithm, you typically try to analyze best-case, worst-case, and average case. If you are trying to communicate this to others, you probably want to list all three to get the full context. Worst case is often what's listed, but average case can be very important. Jan 26 '14 at 6:07

`array_splice` is at worst linear time, but let's assume it's constant time (if it's not, one can write that part differently to make it constant time). The algorithm nevertheless has the same asymptotic complexity as Bubblesort: