Algorithms and Data Structures

Big O

Big Oh O

Big Oh is often used to describe the worst-case of an algorithm by taking the highest order of a polynomial function and ignoring all the constants value since they aren’t too influential for sufficiently large input.

Big Omega Ω

Big Omega is the opposite of Big Oh, if Big Oh was used to describe the upper bound (worst-case) of a asymptotic function, Big Omega is used to describe the lower bound of a asymptotic function. In analysis algorithm, this notation is usually used to describe the complexity of an algorithm in the best-case, which means the algorithm will not be better than its best-case.

Big Theta Θ

When an algorithm has a complexity with lower bound = upper bound, say that an algorithm has a complexity O(n*log(n)) and Ω(n*log(n)), it’s actually has the complexity Θ(n*log(n)), which means the running time of that algorithm always falls in n*log(n) in the best-case and worst-case.

Data Structures

A data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

• Linked List
• Stack
• Queue
• Heap

Algorithms

An algorithm is an unambiguous specification of how to solve a class of problems. It is a set of rules that precisely define a sequence of operations.

Sorting

• Insertion Sort
• Shell Sort
• Bubble Sort
• Shaker Sort
• Comb Sort
• Selection Sort
• Heap Sort
• Quick Sort
• ThreeWayQuick Sort
• IterativeQuick Sort
• Merge Sort
• IterativeMerge Sort
• Tim Sort
• Counting Sort
• PositiveCounting Sort
• Bit Sort
• Radix Sort
• Permutation Sort

Searching

• Linear Search
• Jump Search
• Binary Search
• ...

References

• big O cheatsheet
• google python style guide
• washington edu dsa course
• searching and sorting algorithms
• top algorithms and data structures you really need to know
• itsy bitsy data structures js