Search

Big O Notation

A Big O is a theoratical definition of the complexity of an algorithm as a function of the size. To show the time and space complexity, Big-O, Big-Ω, Big-Θ are commonly used. However, as Big-O shows the worst case scenario, Big-O is the most commonly used method of showing time and space complexity.
O(1)<O(logn)<O(n)<O(nlogn)<O(n)<O(2n)<O(n!)O(1) < O(\log n) < O(n) < O(n\log n) < O(n) < O(2^n) < O(n!)
Best(Fast)<>Worst(Slow)Best (Fast) <---------------> Worst(Slow)

Types of Big-O

Constant Time
Logarithmic Time
Linear Time
Linearithmic Time
Quadratic Time
Exponential Time
Factorial Time

Tips

1.
In computer science, Log base is always 2 (i.e. log2X=Y\log_{2}X=Y)
a.
Unless in special cases (i.e. Terneray Search)
2.
Although some algorithms might have less efficient Big O performance, some prefer these algorithms over other algorithms with better time complexity. Big O is a simple way to show time complexity and cannot be an ultimate decision-making variable. (e.g. Quick vs Merged Sort)
3.
As Big O takes the worst case (inifinty) time complexity
a.
O(n+c)=O(n)O(n + c) = O(n)
b.
O(cn)=O(n)O(cn) = O(n)

Reference

Algorithms and Data Structures Tutorial - Full Course for Beginners
In this course you will learn about algorithms and data structures, two of the fundamental topics in computer science. There are three main parts to this course: algorithms, data structures, and a deep dive into sorting and searching algorithms. By the end, you will understand what algorithms and data structures are, how they are measured and evaluated, and how they are used to solve problems. This course was developed by Pasan Premaratne and Jay McGavren. It was made possible by a grant from teamtreehouse.com ⭐️ Course Contents ⭐️ ⌨️ (0:00:00) Introduction to Algorithms ⌨️ (1:57:44) Introduction to Data Structures ⌨️ (4:11:02) Algorithms: Sorting and Searching ⭐️ Code Snippets for Course ⭐️ 💻 Introduction to Algorithms: ⌨️ Algorithms in Code: 🔗 Linear Search Implementations: https://teamtreehouse.com/library/introduction-to-algorithms/algorithms-in-code/linear-search-implementations 🔗 Binary Search Implementations: https://teamtreehouse.com/library/introduction-to-algorithms/algorithms-in-code/binary-search-implementations 💻 Introduction to Data Structures ⌨️ Exploring Arrays: 🔗 Array Characteristics and Storage: https://teamtreehouse.com/library/introduction-to-data-structures/exploring-arrays/array-characteristics-and-storage 🔗 Operations on Arrays: https://teamtreehouse.com/library/introduction-to-data-structures/exploring-arrays/operations-on-arrays ⌨️ Building a Linked List: 🔗 Singly and Doubly Linked Lists: https://teamtreehouse.com/library/introduction-to-data-structures/building-a-linked-list/singly-and-doubly-linked-lists-2 🔗 Linked List Operations: https://teamtreehouse.com/library/introduction-to-data-structures/building-a-linked-list/linked-lists-operations ⌨️ The Merge Sort Algorithm: 🔗 Merge Sort Implementations: https://teamtreehouse.com/library/introduction-to-data-structures/the-merge-sort-algorithm/merge-sort-implementations 🔗 Alternate Versions of Merge Sort: https://teamtreehouse.com/library/introduction-to-data-structures/the-merge-sort-algorithm/alternate-versions-of-merge-sort ⌨️ Merge Sort and Linked Lists: 🔗 Implementing Merge Sort on Linked Lists: https://teamtreehouse.com/library/introduction-to-data-structures/merge-sort-and-linked-lists/implementing-merge-sort-on-linked-lists 💻 Algorithms: Sorting and Searching ⌨️ Sorting Algorithms: 🔗 Code for Bogosort: https://teamtreehouse.com/library/algorithms-sorting-and-searching/sorting-algorithms/code-for-bogosort 🔗 Code for Selection Sort: https://teamtreehouse.com/library/algorithms-sorting-and-searching/sorting-algorithms/code-for-selection-sort 🔗 Code for Quicksort: https://teamtreehouse.com/library/algorithms-sorting-and-searching/sorting-algorithms/code-for-quicksort 🔗 Code for Merge Sort: https://teamtreehouse.com/library/algorithms-sorting-and-searching/sorting-algorithms/code-for-merge-sort ⌨️ Searching Names: 🔗 Code for Linear Search: https://teamtreehouse.com/library/algorithms-sorting-and-searching/searching-names/code-for-linear-search 🔗 Code for Binary Search: https://teamtreehouse.com/library/algorithms-sorting-and-searching/searching-names/code-for-binary-search -- Learn to code for free and get a developer job: https://www.freecodecamp.org Read hundreds of articles on programming: https://freecodecamp.org/news