Recurrence Relations to Remember

Recurrence                Algorithm                Big-Oh Solution

T(n) = T(n/2) + O(1)      Binary Search            O(log n)

T(n) = T(n-1) + O(1)      Sequential Search       O(n)      

T(n) = 2 T(n/2) + O(1)    Tree traversal       O(n)

T(n) = T(n-1) + O(n)     Selection Sort (other n2 sorts)     O(n2)

T(n) = 2 T(n/2) + O(n)   Mergesort (average case Quicksort)   O(n log n)

T(n) = T(n/2) + O(n)    QuickSelect(select the kth smallest)   O(n)

T(n) = 2 T(n/2) + O(logn)   Optimal Sorted Matrix Search     O(n)

Refer to https://en.wikipedia.org/wiki/Master_theorem for solving more new problems.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s