Big O and Sorting Algorithms

Question 1

describe bubble sort

Answer 1

terrible idea: for n elements, bubble sort O(n^2)

you have to compare each element to every other element

Question 2

linear search

Answer 2

a process that checks every element in a list sequentially until the desired element is found.
BigO time complexity –> O(n)
eliminates one element at a time
necessary when –> it is unknown if list is sorted
example: look for a phrase in a book or manuscript or scroll with no table of contents or page numbers

Question 3

binary search

Answer 3

side note: not appropriate for LinkedLists! since to access a middle element for a LinkedList takes O(n) time. In this case use linear search.

List elements are ordered by the criteria you want to search on.

Takes advantage of the ordering knowledge to eliminate half of the elements with each iteration hence ‘binary’.
BigO time complexity –> O(logn)
Compare middle of list to search element, and continue searching either in bottom half of list or top half of list, iterate until found or reach end of list.

Question 4

divide and conquer algorithm

Answer 4

algorithms that divide problems in half at each step are commonly referred to a ‘divide and conquer’ algorithms

• binary search
• merge sort

Question 5

context of O(logn) vs O(n)

Answer 5

if a list has 1,000,000 an O(log n) search could return “element not found” (worst case scenario) after ~20 iterations, while an O(n) search takes 1,000,000 iterations!

Question 6

selection sort

Answer 6

creates a sorted list by iteratively sorting the list, finding a new minimum on each iteration.
start: index i = 0; find minimum list value for i>=0; place that min in a[0].
next: i=1; find minimum list value for i>=1; place - actually the term used in “swap” = swap places for the min and a[1]
next: i=2….
continue as above until end of list (actually until penultimate item in list)
BigO is O(n^2)
selection sort is easy to understand
selection sort does NOT scale well
(for a list of 1,000 there are ~500,000 comparisons)

Question 7

merge sort

Answer 7

Divide and Conquer algorithm

1. Divide the unsorted list of n elements into sublists that are half of the size of the original list
2. Keep dividing in half until there are n lists, each containing a single element –> This divide part BigO is O(log n)
3. Repeatedly merge the sublists to construct a sorted list with the original size –> This merge part BigO is O(n)

Together BigO is O(nlogn)

more details on other card