Difference between revisions of "W2232 Big-O Notation"
Jeff-strong (talk | contribs) m (Editorial review and minor corrections) |
|||
| (7 intermediate revisions by 3 users not shown) | |||
| Line 7: | Line 7: | ||
== Background == | == Background == | ||
* Watch [https://www.youtube.com/watch?v=D6xkbGLQesk Introduction to Big O Notation and Time Complexity] (CS Dojo) | * Watch [https://www.youtube.com/watch?v=D6xkbGLQesk Introduction to Big O Notation and Time Complexity] (CS Dojo) | ||
* Watch [https://www.youtube.com/watch?v=kgBjXUE_Nwc Getting Sorted & Big O Notation] (Computerphile) | |||
* Read [https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ A beginner's guide to Big O notation] (Rob Bell) | |||
* Watch [https://www.youtube.com/watch?v=RGuJga2Gl_k Why My Teenage Code Was Terrible: Sorting Algorithms and Big O Notation] (Tom Scott) | |||
==Big-O Notation== | |||
Big-O Notation is used to describe the performance of an algorithm and establishes a worst-case run time. It calculates the number of operations performed and the memory required for an algorithm to conclude. Different formulas can be used to calculate the operations performed and memory requirements for each sorting algorithm. Big-O Notation is unable to tell you how long an algorithm will run because too many factors can influence the time an algorithm takes to run. | |||
===Common Formulas=== | |||
'''O(log n)''' - Binary Search | |||
'''O(n)''' - Linear Search | |||
'''O(n * log n)''' - Quicksort | |||
'''O(n<sup>2</sup>)''' - Bubble Sort/Insertion Sort/Selection Sort | |||
{| class="wikitable" | |||
|+ | |||
|- | |||
! Growth Rate !! Name !! Description | |||
|- | |||
| O(1) || Constant || Statement | |||
|- | |||
| O(log(n)) || Logarithmic || Divide in half / Binary search | |||
|- | |||
| O(n) || Linear || Loop | |||
|- | |||
| O(n * log(n)) || Linearithmic || Effective sorting algorithm | |||
|- | |||
| O(n^<sup>2</sup>) || Quadratic || Nested loop | |||
|- | |||
| O(n^<sup>3</sup>) || Cubic || Triple-nested loop | |||
|- | |||
| O(x<sup>n</sup>) || Example || Exhaustive search | |||
|} | |||
Big-O Notation can also be calculated by hand. You can go through each line of code and determine if it will be "1", "log(n)", n, etc. You can then add up all the growth rates, and as one example, it can be expressed as O ( 1 + 3n) where the "1" represents one line of O(1), and the "3n" represents 3 lines of O(n). | |||
{{ComingSoon| | |||
* Timing execution in Linux | |||
}} | |||
== Exercises == | == Exercises == | ||
{{W2232-Exercises}} | {{W2232-Exercises}} | ||
== References == | |||
[https://adrianmejia.com/algorithms-for-dummies-part-1-sorting Big-O Notation for Beginners] (AdrianMejia) | |||
[https://en.wikipedia.org/wiki/Big_O_notation Big-O Notation] (Wikipedia) | |||
Latest revision as of 02:26, 3 April 2022
Prerequisites[edit]
Background[edit]
- Watch Introduction to Big O Notation and Time Complexity (CS Dojo)
- Watch Getting Sorted & Big O Notation (Computerphile)
- Read A beginner's guide to Big O notation (Rob Bell)
- Watch Why My Teenage Code Was Terrible: Sorting Algorithms and Big O Notation (Tom Scott)
Big-O Notation[edit]
Big-O Notation is used to describe the performance of an algorithm and establishes a worst-case run time. It calculates the number of operations performed and the memory required for an algorithm to conclude. Different formulas can be used to calculate the operations performed and memory requirements for each sorting algorithm. Big-O Notation is unable to tell you how long an algorithm will run because too many factors can influence the time an algorithm takes to run.
Common Formulas[edit]
O(log n) - Binary Search
O(n) - Linear Search
O(n * log n) - Quicksort
O(n2) - Bubble Sort/Insertion Sort/Selection Sort
| Growth Rate | Name | Description |
|---|---|---|
| O(1) | Constant | Statement |
| O(log(n)) | Logarithmic | Divide in half / Binary search |
| O(n) | Linear | Loop |
| O(n * log(n)) | Linearithmic | Effective sorting algorithm |
| O(n^2) | Quadratic | Nested loop |
| O(n^3) | Cubic | Triple-nested loop |
| O(xn) | Example | Exhaustive search |
Big-O Notation can also be calculated by hand. You can go through each line of code and determine if it will be "1", "log(n)", n, etc. You can then add up all the growth rates, and as one example, it can be expressed as O ( 1 + 3n) where the "1" represents one line of O(1), and the "3n" represents 3 lines of O(n).
 |
Coming Soon |
|
Exercises[edit]
Write an essay (minimum 500 words) which:
- Defines Big-O
- Compares and contrasts Big-O for:
- Bubble-Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Based upon the above, which sort is most time-efficient for the average case?
Complete your essay in your Journal directory and push to GitHub.
References[edit]
Big-O Notation for Beginners (AdrianMejia)
Big-O Notation (Wikipedia)
