Ещё один частый паттерн в программировании — это рост чего-нибудь в два раза (или в несколько раз). В этом примере внутренний цикл каждый раз, когда до него доходит дело, производит в два раза больше итераций, чем в предыдущий.

Чтобы оценить сложность этого метода, придётся вспомнить из школьной математики формулу для суммы геометрической прогрессии.

\displaystyle 1 + q + q^2 + q^3 + q^4 + ... + q^n = \frac{1 - q^{n+1}}{1 - q} = \Theta(q^n)

Можно запомнить формулу, но досточно лишь такого следствия из неё — скорость роста суммы геометрической прогрессии такая же, как и у последнего члена суммы.

Чаще всего в программировании встречается геометрическая прогрессия с основанием q=2. Для неё все совсем просто!

\displaystyle 1 + 2 + 4 + ... + 2^n = 2^{n+1} - 1 = \Theta(2^n)

Возможно, запомнить этот факт вам станет ещё проще, с такой геометрической интерпретацией:

power-two-sum.

Используйте эти факты в анализе приведённого выше кода.

1. Какая сложность у GetIterationsCount? 1 балл