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[1];
  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. OK, I Understand
 
Top