Lim f(n)/g(n) = 0



lim f(n)/g(n) = 0 --> f(n) o(g(n)) f O Θ =

0< lim --> Ω >=

= inf --> ω >

For a >= 0, b > 0, lim ( lga n / nb ) = 0, so lga n = o(nb), and nb = ω (lga n )

lg(n!) = Θ(n lg n)

|A |B |A ? B |

|5n2 + 100n |3n2 + 2 |Θ |

|log3(n2) |log2(n3) |Θ |

|nlg4 |3lg n |Ω |

|lg2n |n1/2 |O |

Sum1 to n i = n(n+1)/2

Sumi a to b 1 = b-a+1

Sum1 to n i2 = (2n3+3n2+n)/6

Sum1 to n i3 = (n2(n+1)2)/4

Sum1 to n ici = [(n-1)c(n+1) - ncn + c] / (c-1)2

Sum1 to n xi = (xn+1-1)/(x-1)

As n --> inf, and if abs(x) < 1,

Sum1 to n xi = 1/(1-x)

Sum1 to n 1/k (k is int >0) = ln(n) + O(1)

Sum1 to n ixi = x/(1-x)2

Merge: divide until 1 or no elements, merge in order

Insertion: take next input, insert in output at appropriate place (possibly forcing the shift of many values in array)

Shell: insertion sort on partitions of input

Heap: build a heap in Θ(n), getMax in Θ(lg(n)), parent(i) = floor(i/2), left(i) = 2i Heapify costs O(h) where h = lg(n)

*comparison-based sort Ω(nlg(n))*

Counting:

1. for i ( 1 to k

2. do C[i] ( 0

3. for j ( 1 to length[A]

4. do C[A[j]] ( C[A[j]] + 1

5. for i ( 2 to k

6. do C[i] ( C[i] + C[i-1]

7. for j ( length[A] downto 1

8. do B[C[A[ j ]]] ( A[j]

9. C[A[j]] ( C[A[j]] - 1

|Sort |Time |in place |stable |

|merge |Θ(nlg(n)) |0 |1 |

|insertion |O(n2) |1 |1 |

|Shell |Θ(n3/2) |0 |0 |

|Heap |Θ(nlg(n)) |1 |0 |

|Quicksort |Θ(n2)* |1 |0 |

|Counting |O(n) |0 |1 |

|Radix |O(n) |0** |1 |

*best and average are Θ(nlg(n))

** if it uses counting sort

T(n) = T((n/2() + 1 is O(lg n)

T(n) = 2T((n/2( + 17) + n is O(n lg n)

Consider T(n) = 2T((n1/2() + lg n

Rename m = lg n and we have

T(2m) = 2T(2m/2) + m

Set S(m) = T(2m) and we have

S(m) = 2S(m/2) + m ( S(m) = O(m lg m)

Changing back from S(m) to T(n), we have

T(n) = T(2m) = S(m) = O(m lg m) =

O(lg n lg lg n)

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

T(n) ( 3c (n/3( lg (n/3( + n

( c n lg (n/3) + n

= c n lg n - c n lg3 + n

= c n lg n - n (c lg 3 - 1)

( c n lg n

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

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

= n + 3[ n/4 + 3T(n/16) ]

= n + 3[n/4] + 9T(n/16)

= n + 3[n/4] + 9 [n/16] + 27T(n/64)

T(n) ( n + 3n/4 + 9n/16 + … + 3log4 n((1)

( n ( (3/4)i + ((nlog43)

= 4n+ o(n)

= O(n)

Master Method

the recurrence T(n) = a T(n/b) + f(n), T(n) can be bounded asymptotically as follows:

1. If f(n)=O(nlogba-() for some constant ( > 0, then T(n)= ((nlogba).

2. If f(n) = ((nlogba), then T(n) = ((nlogba lg n).

3. If f(n) = ( ( nlogba+( ) for some constant ( > 0, and if a f(n/b) ( c f(n) for some constant c < 1 and all sufficiently large n, then T(n)=((f(n)).

Simplified Master Method

Let a ( 1 and b > 1 be constants and let T(n) be the recurrence

T(n) = a T(n/b) + c nk

defined for n ( 0.

1. If a > bk, then T(n) = (( nlogba ).

2. If a = bk, then T(n) = (( nk lg n ).

3. If a < bk, then T(n) = (( nk ).

Probability

• Sample Space: a set whose elements are elementary events.

For example: flipping 2 coins, S = {HH,HT, TH, TT}.

• Events: a subset A of the sample space S, i.e. A subset S.

• Certain event: S, null event: ø.

• Two events A and B are mutually exclusive, if A intersects B = ø.

• Axioms of Probability: A probability distribution Pr{} on a sample space

S is a mapping from events of S to real numbers such that the following are

satisfied:

1. Pr{A} >= 0 for any event A.

2. Pr{S} = 1.

3. Pr{A union B} = Pr{A} + Pr{B} for any two mutually exclusive events

A and B.

Pr{A} is the probability of event A. Axiom 2 is a normalization requirement.

Axiom 3 can be generalized to the following:

•

Pr{U Ai} = Sum Pr{Ai}

• Pr{ ø } = 0

• If A subset B, then Pr{A} ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download