• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Jan 23rd, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. 1.
2. A[1...n]
3. int x
4. int y
5. int z
6. int a=0
7. for i=1 to z do
8.     if(x==0)
9.         if(A[i]<x)
10.             a=a+1
11.     else for j=y to z
12.             if(A[i]==j)
13.                 break
14.     if(z!=0)
15.         if(A[i]<x)
16.             a=a+1
17.
18. T(n) = O(n^2) - worst case becouse loop isn't breaked by the condition  so it must repeat n^2-times.
19. 2. A[1...n]
20.     product(A, n)
21.         if(n==1)
22.             return A;
23.         else
24.             return(A, n-1)*A[n]
25.     T(4)=T(3)=T(2)=T(1)
26.     T(n)=O(n)
27. 3.(wklej od szymka popraw fory)
28. 4.a)
29. b)  a=8, b=2, f(n) = n
30.     n^logb (a) = n^log8 2 = n^3
31.     f(n)=n < n^3 - czyli dużo O bo epsilon > 0
32.     theta(n^log8 2) = theta(n^3)
33. c)a=4 b=2 f(n)=n^4
34.     n^logb(a) = n^log2 4 = n^2
35.     f(n) = n^4 > n^2 czyli omega ale nie chce mi sie sprawdzac warunku
36.     theta(f(n))=theta(n^4)
37. d)
38. 5.
39. BUBBLE-SORT(A,n)
40. for i=n downto 2
41.     for j=1 to i-1
42.         if A[j] > A[j+1]
43.             A[j] ← → A[j+1]^3                ← swap
44.
45. T(n) = theta(n^2)
46. INSERTION-SORT (A, n)
47.     for j = 2 to n
48. r = A [j]
49. i = j − 1
50.         while i >= 0 and A[i] > r do
51.             A[i + 1] = A[i]
52. i = i − 1
53. A[i + 1] = r ^3
54.
55. B(n) = theta(n)
56. T(n) = O(n^2)
57. W(n) = theta(n^2)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top