Задача: (перевожу с французского, может быть не совсем похоже на русский вариант но идея таже).
Вы разработали алгоритм который уменьшает компонент проблемы размером n в 3 еденицы времени, в компонент той же проблемы размером n - 1.

a)
Напишите рекурентное отношение для T(n), время которое берет ваш алгоритм для проблемы размером n.

б)
Определите T(n) решив это рекурентное отношение методом итерации (подстановкой). Известно что проблема размером 1 может быть решена в одну еденицу времени. Дайте также ответ для T(n) в асимптотической форме (big-O).

Решение:

а)
На скока я понял есть такая формула: T(n) = aT(n/b) + f(n)
Изходя из этого у меня получилось следующее: T(n) = 3T(n - 1) + n
Тут я не уверен что это правильно, пожалуйста проверьте.

б)
известно что T(1) = 1
начинаем с подстановки (n - 1) за место n:

1. T(n) = 3T(n - 1) + n;
2. T(n) = (3T(n - 2) + n) + n;
3. = ((3T(n - 3) + n) + n) + n;
4. = T(1) + n + ... + n;
5. = 3T(n - (n - 1)) + n(n - 1);
6. = 1 + n^2 - n;
7. = n^2 - n + 1;
8. = n^2;
9. = O(n^2);

тут не понимаю начиная с 4ой строчки. Вобще правильно для начала решено или нет. Делал по примеру с лекции, до конца в деталях не понимаю. Поэтому возможны ошибки.