How to determine the algorithmic complexity of a function?

Question

PHP

I have a function, I need to determine its algorithmic complexity, I seem to have read the literature, but I don’t understand how to arrange it. Help with this example please.

<?php
function get_array_group_of_words(array $words) {        
    
    usort($words, function($a, $b) {
        return strlen($b) - strlen($a);
    });
    
    $group_of_words = [];
    $this_group = false;
    
    foreach($words as $key => $value) {
        if (!is_string($value))
            throw new \InvalidArgumentException('Массив может содержать только строки.');
        
        if ($this_group) {            
            $last = array_pop($group_of_words);
            $last[] = $value;
            array_push($group_of_words, $last);
        } else {
            
            $group_of_words[] = [$value];
        }
                
        if (isset($words[$key+1])) {
            
            $word1 = preg_split('/(?<!^)(?!$)/u', mb_strtolower($value));
            sort($word1);
            $word2 = preg_split('/(?<!^)(?!$)/u', mb_strtolower($words[$key+1]));
            sort($word2);
            
            if (strcmp(implode('', $word1), implode('', $word2)) == 0) {
                $this_group = true;
            } else {
                $this_group = false;
            }
        }
    }
    
    return $group_of_words;
}

Answer 1

To determine the algorithmic complexity of a function, add the algorithmic complexity of the functions included in it. What's in the loop - multiply by the number of iterations.
If you read it, what is the complexity of strlen?

Answer 2

Inside the foreach, strcmp is used, which has O(N)
complexity. The loop also has this complexity. Complexities of nested algorithms are multiplied:
O(kN^2 + nlogn)
k - the number inside algorithms with complexity O(N), since there are strtolower, preg_split, etc., then, accordingly, the cycle O(N*(N + N + ... N)) (difficulties are summed within one block)
nlogn - because of usort, I don't know what algorithm is used there, so let's take the fastest one.
As a result, we round up to the value that gives the largest contribution, since with growth the sum nlogn becomes insignificant, as does the multiplier k, then: O(N^2) answer
You take it in a loop, increase the size of the input data and measure the speed of execution, build a graph where you set aside time for Y, and N for X, and usually the points lie within any function: y=N;Y=N^2;Y=logN, etc. .d

Answer 3

Cyclomatic complexity (suddenly pushes the right one)

Answer 4

It upsets me:
1) the lack of a description of what this function does
2) the strange code for determining the equality of words
3) the use of the this_group flag is
not strong in PHP, but I rewrote it a little better:

// hash as sorted chars of word
// i.e. 'ababcad' -> 'aabbcd'
function word_hash($word) {
    $chars = str_split($word);
    sort($chars);
    
    return implode($chars);
}

// return grouped by word_hash array of words
function get_words_grouped_by_chars($words) {
    $hashes = [];
    $group_of_words = [];
    
    foreach($words as $key => $value) {
        if (!is_string($value))
            throw new \InvalidArgumentException('Массив может содержать только строки.');
        $hash = word_hash($value);
        if (!array_key_exists($hash, $hashes)) {
            $hashes[$hash] = $value;
            $group_of_words[$hashes[$hash]] = []; 
        }
        array_push($group_of_words[$hashes[$hash]], $value);
    }
    
    uksort($group_of_words, function($a, $b) { return strlen($b) - strlen($a); });
    return array_values($group_of_words);
}

the complexity is O(N) linear since only one loop is used. BUT! if there is a need to estimate the complexity straight away (together with array_push, uksort and others) - then the complexity for the most complex element (uksort) is most likely O(N logN), you need to look at the documentation