Что такое Big O время выполнения двух следующих решений

Я придумал 2 решения для следующего вопроса интервью

Given 2 different lists of integers, write a function that will return their intersection.

Решение 1:
С помощью приведенного ниже кода я сортирую оба списка, а затем перебираю их с двумя счетчиками (по одному на список). Увеличьте указатель, который указывает на меньшее значение. Если оба указателя указывают на одно и то же значение, вставьте его в результат и увеличьте оба указателя. (Возвращает отсортированные пересечения)

<?php

function find_intersection($a1, $a2) {

$intersection = array();
sort($a1);
sort($a2);

$i = $j = 0;
while($i < count($a1) && $j < count($a2)) {
if($a1[$i] > $a2[$j]) {
$j++;
} else if($a1[$i] < $a2[$j]) {
$i++;
} else {
$intersection[] = $a1[$i];
$i++;
$j++;
}
}
return $intersection;
}
?>

Решение 2:
Здесь я перебираю первый список, помещаю значения в массив, используя значение в качестве ключа, и счет в качестве значения (если
он уже находится в списке приращений на единицу, иначе введите 1). Затем выполните итерацию list2, если значение находится в
hashtable и> 0 вставляют это значение в массив результатов, уменьшая значение в хеш-таблице.

Ниже решение 2 вернет НЕПРАВИЛЬНОЕ пересечение

function find_intersection2($a1, $a2) {
$hash_arr = array();
$intersection = array();
for($i = 0; $i < count($a1); $i++) {
if(isset($hash_arr[$a1[$i]])) {
$hash_arr[$a1[$i]]++;
} else {
$hash_arr[$a1[$i]] = 1;
}
}

for($j = 0; $j < count($a2); $j++) {
if(isset($hash_arr[$a2[$j]])) {
$intersection[] = $a2[$j];
$hash_arr[$a2[$j]]--;
}
}

return $intersection;
}

Вопрос 1)
Какой будет среда выполнения решения № 1? Это O (n log n) из-за сортировки? Как бы вы проанализировали это? Объясни это пожалуйста.

Вопрос 2)
Для решения № 1, если бы я точно знал, что массивы, которые я получу, будут отсортированы и их не нужно будет сортировать, будет ли решение тогда O (n) из-за итерации цикла while?

Вопрос 3)
Для решения 2 это большой O (n), потому что я запускаю 2 отдельных цикла?