Какое худшее время работы для данного алгоритма

Question

Мне задали этот вопрос в моей научной статье. пожалуйста, дайте мне знать ответ?

arrayFind(x, A) 
    i =0 ; 
    while(i < n) { 
     if(x==A[i]) 
      return i; 
     else 
      i = i+1; 
    } 
return –1; 

Предположим, что у нас есть алгоритм, find2D(), чтобы найти элемент x в два мерных n x n массива A. Алгоритм find2D() выполняет итерацию по строкам A и вызывает алгоритм arrayFind() на каждом из них, пока не будет найдено x или он выполнил поиск по всем строкам A.

Что наихудшее время работы этого алгоритма

а. Если элементы в каждой строке сортируются?
b. Если элементы в каждой строке не отсортированы?

Answer 1

С учетом приведенной информации сортировка/не сортировка не влияет на сценарий наихудшего случая. В обоих случаях наихудший случай будет заключаться в том, что последний элемент последней строки - тот, который нужно найти. В этом случае время выполнения будет O (n^2), где n имеет значение, указанное вами с n x n. Это n x n, потому что вам нужно перебирать строки n, а затем делать n сравнения в каждой строке.

Если вы использовали бы двоичный поиск, отсортированный пример имел бы наихудшее время выполнения O (n log n), а наихудший случай был бы таким, чтобы искомый элемент находился посередине последней строки.