Standard big o notations.md

Big Theta Notation: Actual complexity. Big O Notation: Worst case complexity. Big Omega notation: Best ase complexity.

Standard function asymptotic analysis.

• Constant: O(1)
• Linear: O(N)
• One nested loop: O(N^2)
• Binary Tree Search: O(Log N)
• Simple recursive function: O(N)
• Fibonacci recursive function: O(2^N)
• Fibonacci2 loop function: O(N)

Standard data structures.

Dynamic Arrays

Operations:

• Add O(N)
• Remove O(N)
• Find O(N)

Dynamic arrays are a managed implementation of static arrays. This leads us to a number of complexities when assessing performance.

For data sets that are constantly changing dynamic array adding and removing on a regular basis comes at a very high cost.

Linked Lists

Operations:

• Add O(1)
• Remove O(1)
• Find O(N)
• Merging two lists O(1).

Modifying the list saves huge amounts of time with adding and removing and merging!

Searching is slow. Pointer overheads.

Priority Queue

• Add O(Log N)
• Remove O(Log N)
• Find min O(1)

A minimum priority queue is often managed as a binary tree.

Hash Table

Unorder hash value. Prevent duplication.

• Add O(1)
• Remove O(1)
• Find O(1)