Расчет Theta (п) алгоритма

Question

Я пытаюсь вычислить Theta (п) следующего алгоритма

for i = 1 -> n 
    for j = 1 -> n 
     B[i,j] = findMax(A,i,j) 

findMax(A,i,j) 
    if j < i 
     return 0 
    else 
     max = A[i] 
     for k = i + 1 -> j 
      if max < A[k] 
       max = A[k] 
     return max 

Я знаю, что O, тета, и омега примерно перевести

O ≈ ≤

Ω ≈ ≥

Θ ≈ =

Для алгоритма я думаю что omega = n^2, o = n^3, но я не уверен, что такое тета. Есть идеи?

Answer 1

Если подсчитать количество раз, строку кода

if max < A[k] 

выполняется в зависимости от n вы получите Theta (п^3) исполнение. Таким образом, время работы вашего алгоритма - это Thetat (n^3).

Answer 2

Theta (n^3). Существует n^2 итераций вложенного цикла. Примерно половина этих итераций выполняется в O (1) раз, когда j < i. Другая половина этих итераций имеет в среднем n/2 разницу для j-i, поэтому другая половина итераций принимает время Theta (n/2). Так как примерно половина из n^2 итераций занимает среднее n/2 времени, n^2/2 * n/2 = n^3/4 = Theta (n^3) время для половины итераций. Другая половина n^2 -тераций принимает n^2/2 = Theta (n^2) раз. Таким образом, общее время выполнения = Theta (n^3).