Поиск функции счетчика шагов с функциями потолка / пола

Question

Я столкнулся с проблемой в учебнике, с которой у меня проблемы.Мне нужно найти функцию подсчета шагов в терминах n, которая подсчитывает, сколько раз вызывается процедура печати.Ниже приведен псевдокод.

function EXAMPLE( some positive int n )
 i <- 1
 while i <= n do
      i <- i * 2
      j <- 1
      while j <= i do
          j <- j + 1
          print("something")

Я попытался начать с определения количества вызовов функции print для n в некоторых случаях:

n  T(n)
1   2
2   6
3   6
4   14
5   14

Я уверен, чтоФункция floor / floor с n задействована каким-то образом для первого цикла while, но я не уверен, что делать дальше.Любая помощь приветствуется.

Answer 1

Внутренний цикл: j увеличивается с 1 до i --- работает i раза.

Внешний цикл: классический логарифмический цикл. i увеличивается как степень двух, пока не станет больше или равным n.

Так что ваше предположение было верным. Обратите внимание, что i удваивается до внутреннего цикла, а не после; это приводит к удвоению количества звонков. Общее количество звонков на номер print составляет:

Тестовые значения:

n    T(n)
----------
1    2
2    6
3    6
4    14
5    14
6    14
7    14
8    30
9    30
10   30
...

Из-за оператора на этаже T(n) увеличивается только тогда, когда n достигает следующей степени 2.