edX: - HarvardX: CS50x3 Introduction to Computer Science - week 3 Continue

Obama was not totally wrong when it came to answering a Computer Science question.



bubblesort
(n(n-1))/2
big O    - eg  order of n^2   or O(n^2)

O(n) - finding maximum number in a list
O(log n)  -eg  phonebook -approximately decreases  problem in half every step - list has to be sorted 
O(1)  -  constant

lower bound (n) or   Ω(n)  - eg  bubblesort
lower bound (1)  - phonebook
selection sort -    upper bound and lower bound of n^2
insertion sort -  upper bound and lower bound of n^2
merge sort - eg sort left, sort right and merge  O(n log(n))  which is much faster

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.