Решение PermCheck Codility Scala

Question

в первую очередь.Я знаю, что этот вопрос задавали много.Это касается урока PermCheck веб-страницы codility.Ссылку можно найти здесь: https://app.codility.com/programmers/lessons/4-counting_elements/perm_check/

Причина моего вопроса довольно проста: он проваливает проверку производительности, заявляя следующее: Обнаружена временная сложность: O (N ** 2).

Если вы посмотрите на мой код, я использую HashSet и рекурсивно перебираю массив только один раз.Поэтому я не могу понять, откуда исходит временная сложность O (N ^ 2).Более того, я уже видел в ответе людей, которые говорят, что использовали «For» и «HashSet» и получают 100%.

Может быть, это также учитывает сложность пространства, но это ошибочная ошибка?

def permCheck(a: Array[Int]): Int = {
   def maxAndHash(a: Array[Int], hash: HashSet[Int], max: Int, acc: Int): Option[(Int, Int)] = a match {
  case Array() => Some((max, acc))
  case _ => {
    val head = a.head
    if (hash.contains(head)) None
    else maxAndHash(a.tail, hash + head, if (max < head) head else max, acc + 1)
  }
}

maxAndHash(a, HashSet[Int](), Int.MinValue, 0) match {
  case None => 0
  case Some((max, acc)) => if (acc == max) 1 else 0
  }
}