Дайте точный и асимптотический ответ для псевдокода ниже.

Question

for i <--- 1 step i <--- 2* i while i< n do 
  for j <--- 1 step j <---2* j while j<n do 
    if j = 2*i 
      for k = 0 step k <--- k+ 1 while k < n do 
        .... CONSTANT NUMBER OF ELEMENTARY OPERATIONS 
      end for 
    else 
      for k<--- 1 step k<-- 3*k while k<n do 
        ...CONSTANT NUBER OF ELEMENTARY OPERATIONS 
      end for 
    end if 
  end for 
end for

Каково время выполнения следующего фрагмента кода в зависимости от n?

«Точный ответ» относится к уравнению, связанному с кодом, ДО того, как вы определите время асимптотики.

Answer 1

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

Вы не можете точно оценить время работы, поскольку оно сильно зависит от вашей системы.