жесткая (Θ) граница

Question

Может кто-нибудь объяснить это мне? Такие как это:

С учетом функции:

for k = 1 to lg(n)
  for j = 1 to n
    x=x+1

Как бы я проанализировал жесткую (Θ) границу?

Answer 1

Ваша функция Θ (log n · n ): внешний цикл повторяется log n раз, а внутренний цикл n раз (для каждой итерации внешнего for), поэтому x=x+1 выполняется в журнале n · n всего. А поскольку количество повторений фиксировано, нижняя и верхняя границы одинаковы.