Помощь с лабораторной работой по Алгоритмам и структурам данных

Лабораторная работа 2. Рекуррентные уравнения.

Задание 1. Решить следующие рекуррентные уравнения:

1) T( n) =4T(2n/3) + 1, T(1) = 3

T( n) = T(n-1) + lg n, T(1) = 4

T( n) = T(n/3) + T(3n/5) + n

2) T( n) = T(n-1) + n2, T(1) = 1

T( n) = 3T(3n/4) + n, T(1) = 1

T( n) = T(n/6) + T(3n/4) + n2

Задание 2. Определите верхнюю и нижнюю асимптотические границы функции T( n) для каждого из перечисленных ниже рекуррентных соотношений. Считаем, что T( n) - константа при достаточно малых n. Обоснуйте свой ответ.

1) T( n) = 2T(n/2) + n3

T( n) = 7T(2n/5)+n2

T( n) = 2T(n/4) +n1/2

2) T( n) = T(9n/10) + n

T( n) = 6T(n/2) + n2

T( n) = 16T(n/4) + n2

Задание 3*. Решить следующее рекуррентное уравнение:

T( n)=T(n/a)+T(n/b)+nk, a>1,b>1,k≥1.