как вычислить временную сложность в большой нотации O этого алгоритма

Question

мне нужна помощь в поиске временной сложности этой функции в большой нотации O:

int myfunction(bool exists) 
{ 
    int var=0; int k,j,n; 
    if (exists) 
     for(k=1; k<=n; k*=2) 
      for(j=1; j<=k; j++) 
      var++; 
    else 
     for(k=1; k<=n; k*=2) 
      for(j=1; j<=n; j++) 
      var++; 
    return var; 
} 

от того, что я понял из книги, в тех случаях, как это, когда мы имеют блоки if-else, общая сложность алгоритма - худший случай обоих блоков, поэтому я вычислил сложность блока else, которая имеет сложность O (log2 (n)), исправьте меня, если я ошибаюсь , но у меня возникли проблемы с поиском временной сложности блока if, кажется, что это занимает меньше времени, но я не могу определить, сколько.

Answer 1

формальный ответ был бы, отделяя блок IF и блок ELSE:

Answer 2

В противном случае вы выполняете n * floor (log 2 (n)) раз. Поскольку мы хотим big-O, мы берем худший случай, где floor (log 2 (n)) == log2 (n). Следовательно, петля else - O (n log2 (n)). На самом деле я бы обычно писал O (n log (n)) здесь - в большой записи O вы не ставите постоянные факторы, например, изменение базы журнала.

В случае if внутренний цикл работает 1, 2, 4, ..., 2^x раз, где x - пол (log2 (n)). Общее число циклов является суммой этих чисел, т. Е. 2 ​​^ (x + 1) -1. Если вы не видите этого сразу, обратите внимание, что 1, 2, 4 и т. Д. Являются просто двоичными цифрами. Если вы заполните эти цифры, то что общего? Вы увидите, что это двоичное число, такое как 11111.

Следовательно, цикл if принимает 2^(пол (log 2 (n)) + 1) - 1 шаг; беря наихудший случай, это 2^(log 2 (n) + 1) - 1 = 2n - 1. Сохраняя наибольший член и понижая константы, это O (n).