比较两个字符串的复杂性

Question

$haystack = array('T', 'h', 'i', 's', 'i', 's', 's', 'r', 'i', 'k', 'a', 'n', 't', 'h');
$needle = array('s', 'r', 'i', 'k', 'a', 'n', 't', 'h');
$array = array();
$k = -1;

$m = count($needle);
$n = count($haystack);
//****************1st type********************
for ($i = 0; $i < $m; $i++) {
    for ($j = 0; $j < $n; $j++) {
        if ($needle[$i] == $haystack[$j]) {
            $array[++$k] = $needle[$i];
            //echo $needle[$i]."<br/>";
            break;
        }
    }
}
//********************2nd type**************************
$found_array = array();
$j = 0;
for ($i = 0; $i < $n; $i++) {
    if ($needle[$j] == $haystack[$i]) {
        $found_array[] = $needle[$j];
        $j++;
    }
}

echo '<pre>';
print_r($array);
echo '</pre>';

echo '<pre>';
print_r($found_array);
echo '</pre>';

As you could see I am comparing 2 strings...using 2 different types. what is complexity of each of them? My answer is O(NM) for both..Am I correct???

Answer 1

the top one is O(NM) because you have the two nested for loops.

The bottom one is O(N) as you only traverse the needle array.