Алгоритмы, оценка сложности функции

Question

Покажите, что для произвольной константы c > 0 функция g(n) = 1 + c + c^2 + ... + c^n есть
(а) Θ(1), если с < 1;  
(b) Θ(n), если c = 1;  
(c) Θ(c^n), если c > 1.
Другими словами, в сумме убывающей геометрической прогрессии можно оставить лишь первый член; возрастающей - последний, а постоянной - количество членов.

Подскажите, пожалуйста, с чего начать? Есть ли какой-то универсальный метод для всех трех случаев?

Answer 1

Ничего сложного нет просто подставьте значения и подсчитайте что получится. Имея g(n) = 1 + c + c^2 + ... + c^n и формулу для суммы членов геометрической прогрессии

Θ(1), если с < 1;

Если считать g(n) бесконечной суммой, то можно применить формулу суммы бесконечной убывающей геометрической прогрессии

откуда имеем следующее,

g(n) = 1 + c + c^2 + ... + c^n < 1/(1-с) = O(1) не зависит от n.
Θ(n), если c = 1;
В этом случае подставив c = 1

g(n) = 1 + c + c^2 + ... + c^n = 1 + 1 + 1 + ... + 1 = 1 + n = O(n)
Θ(c^n), если c > 1.

Просто подставив в формулу суммы членов геометрической прогрессии

g(n) = 1 + c + c^2 + ... + c^n = (1-с^n)/(1-с) = (c^n -1)/(c-1) = c^n/(с-1) - const = const*c^n - const = O(с^n), где const = 1/(с-1)

БЛОГ НА HUSL

Алгоритмы, оценка сложности функции

Ответы (1 шт):