Упражнения

Which of the following statements is/are valid?

1.Time Complexity of QuickSort is Θ(n^2)

2.Time Complexity of QuickSort is O(n^2)

3.For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).

4.Time complexity of all computer algorithms can be written as Ω(1)

http://quiz.geeksforgeeks.org/algorithms/analysis-of-algorithms/

1) С помощью основной теоремы рекуррентных уравнений решить следующий соотношения

1. $$ T (n) = 3T (n/2) + n^2$$
2. $$T (n) = 4T (n/2) + n^2$$
3. $$T (n) = T (n/2) + 2^n$$
4. $$T (n) = 2nT (n/2) + n^n$$
5. $$T (n) = 16T (n/4) + n$$
6. $$T (n) = 2T (n/2) + n \log n$$
7. $$T (n) = 2T (n/2) + n/ \log n$$
8. $$T (n) = 2T (n/4) + n^{0.51}$$
9. $$T (n) = 0.5T (n/2) + 1/n$$
10. $$T (n) = 16T (n/4) + n!$$
11. $$T (n) = \sqrt{2} T (n/2) + \log n$$
12. $$T (n) = 3T (n/2) + n$$
13. $$T (n) = 3T (n/3) + \sqrt{n}$$
14. $$T (n) = 4T (n/2) + cn$$
15. $$T (n) = 3T (n/4) + n \log n$$
16. $$T (n) = 3T (n/3) + n/2$$
17. $$T (n) = 6T (n/3) + n^2 \log n$$
18. $$T (n) = 4T (n/2) + n/ \log n$$
19. $$T (n) = 64T (n/8) − n^2 \log n$$
20. $$T (n) = 7T (n/3) + n^2$$
21. $$T (n) = 4T (n/2) + \log n$$
22. $$T (n) = T (n/2) + n(2 − \cos n)$$

Ответы

1. $$T (n) = 3T (n/2) + n^2 \Longrightarrow T (n) = \Theta (n^2) \, (Case \, 3)$$

2. $$ T(n) = 4T (n/2) + n^2 \Longrightarrow T (n) = \Theta(n^2 log n) \, (Case \, 2)$$

3. $$ T (n) = T (n/2) + 2n \Longrightarrow T(n) = \Theta (2^n) (Case \, 3)$$

4. $$ T (n) = 2n T (n/2) + n^n \Longrightarrow \, Does \, not \, apply \, (a \, is \, not constant)$$

5. $$T (n) = 16T (n/4) + n \Longrightarrow T (n) = \Theta(n^2 ) (Case 1)$$

6. $$T (n) = 2T (n/2) + n \log n \Longrightarrow T (n) = n \log ^2 n (Case 2)$$

7. $$T (n) = 2T (n/2) + n/ \log n \Longrightarrow Does \, not \, apply \, (non-polynomial \, difference \, between \, f(n) \, and \, n^{\log_b a} )$$

8. $$T (n) = 2T (n/4) + n ^{0.51} \Longrightarrow T (n) = \Theta(n^{0.51}) (Case 3)$$

9. $$T (n) = 0.5T (n/2) + 1/n \Longrightarrow Does not apply (a < 1)$$

10. $$T (n) = 16T (n/4) + n! \Longrightarrow T (n) = \Theta(n!) (Case 3) $$

11. $$T (n) = \sqrt{2}T (n/2) + \log n \Longrightarrow T (n) = \Theta(\sqrt{n}) (Case 1)$$

12. $$T (n) = 3T (n/2) + n \Longrightarrow T (n) = \Theta(n^{\log 3} ) (Case 1)$$

13. $$T (n) = 3T (n/3) + \sqrt{n} \Longrightarrow T (n) = \Theta(n) (Case 1)$$

14. $$T (n) = 4T (n/2) + cn \Longrightarrow T (n) = \Theta(n^2 ) (Case 1)$$

15. $$T (n) = 3T (n/4) + n \log n\Longrightarrow T (n) = \Theta(n \log n) (Case 3)$$

16. $$T (n) = 3T (n/3) + n/2 \Longrightarrow T (n) = \Theta(n \log n) (Case 2)$$

17. $$T (n) = 6T (n/3) + n^2 \log n \Longrightarrow T (n) = \Theta(n^2 \log n) (Case 3)$$

18. $$T (n) = 4T (n/2) + n/ \log n\Longrightarrow T (n) = \Theta(n^2 ) (Case 1)$$

19. $$T (n) = 64T (n/8) − n^ 2 \log n \Longrightarrow Does not apply (f(n) is not positive)$$

20. $$T (n) = 7T (n/3) + n^2 \Longrightarrow T (n) = \Theta(n^2 ) (Case 3)$$

21. $$T (n) = 4T (n/2) + \log n\Longrightarrow T (n) = \Theta(n^2 ) (Case 1)$$

22. $$T (n) = T (n/2) + n(2 − \cos n) \Longrightarrow$$ Does not apply. We are in Case 3, but the regularity condition is violated. (Consider n = 2πk, where k is odd and arbitrarily large. For any such choice of n, you can show that c ≥ 3/2, thereby violating the regularity condition.)