Difference between revisions of "W2232 Big-O Notation"

From Coder Merlin
(One intermediate revision by the same user not shown)
Line 10: Line 10:
* Read [https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ A beginner's guide to Big O notation] (Rob Bell)
* 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)
* 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. There are different formulas 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 there are too many factors that influence the time an algorithm takes to run.
===Common Formulas===
'''O(log n)''' - Binary Search
'''O(n)''' - Simple Search/ Bubble Sort
'''O(n * log n)''' - Quicksort
'''O(n<sup>2</sup>)''' - 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 all of the growth rates together and it can be expressed as, for example, O(1+3n) where the "1" represents one line of O(1), and the "3n" represents 3 lines of O(n).


{{ComingSoon|
{{ComingSoon|
Line 17: Line 51:
== 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)

Revision as of 00:08, 1 May 2021

Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder
Big-O

Prerequisites[edit]

Background[edit]

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. There are different formulas 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 there are too many factors that influence the time an algorithm takes to run.

Common Formulas[edit]

O(log n) - Binary Search

O(n) - Simple Search/ Bubble Sort

O(n * log n) - Quicksort

O(n2) - 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 all of the growth rates together and it can be expressed as, for example, O(1+3n) where the "1" represents one line of O(1), and the "3n" represents 3 lines of O(n).

ComingSoonIcon.png
Coming Soon
  • Timing execution in Linux

Exercises[edit]

ExercisesExercisesIcon.png

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)