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) T`ree traversal *O(n)*

`T(n) = T(n-1) + O(n) `Selection Sort (other n^{2} sorts) *O(n ^{2})*

`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