Решить вариант по анализу алгоритмов

2. Расположите следующие функции по порядку в соответствии с нотацией большого О (обоснуйте это расположение). Сгруппируйте, например, с помощью подчеркивания, функции, которые являются ? оценкой друг другу:
1) 10 n log n;
2) 2100;
3) 200logn;
4) n 2n;
5) log(n!);
6) n!;
7) nlog log n.
3. Для каждой функции f(n) = {log n, n1/2, n, n log n, n2, 2n, n!} и времени t (1 секунда, 1 час, 1 неделя, 1 год, 1 столетие) определите наибольший размер n задачи, которая может быть решена за время t, при условии, что для ее решения алгоритму необходимо f(n) микросекунд. Результат представьте в виде таблицы.
4. Покажите, что для любых действительных констант a и b, где a, b > 0, справедливо соотношение (n+a)b= ? (nb).
5. Пусть f(n) и g(n) – асимптотически положительные функции. Докажите или опровергните справедливость каждого из приведенных ниже утверждений:
1) f(n) = O (f(n)2);
2) из f(n) = O (g(n)) следует, что g(n) = ? (f(n));
3) f(n) = ? (f(n/2));
4) из f(n) + o(f(n))= ?(f(n)).
6. Выразите функцию f(n)=3n2/1000+10 n logn+200 n+3 в ? обозначениях.
7. С помощью метода рекурсивных деревьев, докажите, что решение рекуррентного соотношения T (n) = T (n/3) + T (2n/3) + c n ведет себя как ? (n logn), где с – константа.
8. Определите верхнюю и нижнюю асимптотические границы функции T (n) для каждого из представленных ниже рекуррентных соотношений. Считаем, что T (n) – константа при достаточно малых n. Обоснуйте свой ответ.
1) T (n) = 2 T (n/2)+ n3;
2) T (n) = 7 T (2n/5)+ n2;
3) T (n) = 2 T (n/4)+ n1/2.