Ещё один частый паттерн в программировании — это рост чего-нибудь в два раза (или в несколько раз). В этом примере внутренний цикл каждый раз, когда до него доходит дело, производит в два раза больше итераций, чем в предыдущий.
Чтобы оценить сложность этого метода, придётся вспомнить из школьной математики формулу для суммы геометрической прогрессии.
Можно запомнить формулу, но досточно лишь такого следствия из неё — скорость роста суммы геометрической прогрессии такая же, как и у последнего члена суммы.
Чаще всего в программировании встречается геометрическая прогрессия с основанием q=2. Для неё все совсем просто!
Возможно, запомнить этот факт вам станет ещё проще, с такой геометрической интерпретацией:
.
Используйте эти факты в анализе приведённого выше кода.
Войдите или зарегистрируйтесь, чтобы отвечать на тесты и решать задачи.