Немного потерялся в этом вопросе. Если бы второй член был T ((1-a) n), я бы решил его, потому что это всего лишь вариант «разделяй и властвуй». Но здесь это отрицательное значение.
То, что я сделал, просто принято за 0, потому что в контексте алгоритма отрицательный размер ввода не имеет смысла. Это дает мне -
T (n) = T (an) + sn
Первый член будет приближаться к нулю, а константы дадут мне GP, который можно легко суммировать. В целом ответ, который я получил с точки зрения асимптот, - O (sn)
Это правильный способ решить эту проблему? Есть ли способ решить ее, не пренебрегая вторым слагаемым?