Category Archives: Data-structures

Final review

Asymptotic complexity Upper bound function Lower bound function Order function Solving recurrence equations Sorting Insertion sort – algorithm, complexity and benefits Selection sort – algorithm, complexity and benefits Quicksort – algorithm, complexity and benefits Mergesort – algorithm complexity and benefits … Continue reading

Posted in Data-structures | Comments Off

Mergesort and Quicksort

Mergesort (not an in-place sort) mergesort(a, i, j) {       if (i >= j) return;       mid = (i + j)/2;       mergesort(a, i, mid);       mergesort(a, mid + 1, j);       merge(a, i, j); } merge(a, i, j) { … Continue reading

Posted in Data-structures | Comments Off

Trees and Graphs

Here are definitions of some of the common terms you would often encounter in the context of trees and graphs. Trees Tree: A set of nodes and edges connecting the nodes such that there is exactly one path between any … Continue reading

Posted in Data-structures | Comments Off

Growth of functions

In algorithmic analysis, we learn to characterize the complexity in terms of an upper bound (Big-oh), a lower bound (Big-omega) and an order function (Big-theta). Here are the definitions: 1. Upper bound function (i.e., T(n) is upper-bounded by f(n)): We … Continue reading

Posted in Data-structures | Comments Off