Midterm Flashcards
Summarize Selection Sort
Best Case: (1/2)N^2
Average Case: (1/2)N^2
Worst Case: (1/2)N^2
Stability: No
In-Place: Yes
Improvement: None
Summarize Insertion Sort
Best Case: N
Average Case: (1/4)N^2
Worst Case: (1/2)N^2
Stability: Yes
In-Place: Yes
Improvement: Move Large Entries to the right one space rather than doing full exchanges
Advantage: Good for small arrays
Summarize Shell Sort
Best Case: Nlog_3(N)
Average Case: N/A
Worst Case: cN^(3/2)
Stability: No
In-Place: Yes
Improvement: N/A
Advantage: Good for very large arrays
Summarize Merge Sort
Best Case: (1/2)Nlog(N)
Average Case: Nlog(N)
Worst Case: Nlog(N)
Stability: Yes
In-Place: No
Improvement: Insertion Sort for Small Subarrays
Summarize Quick Sort
Best Case: Nlog(N)
Average Case: Nlog(N)
Worst Case: N^2
Stability: Yes
In-Place: Yes
Improvement: Cutoff to Insertion
How do you determine the time complexity relationship between two functions f and g?
take the limit of (f(n)/g(n)) as n goes to infinity. Let’s say that value is L
If L = 0 then f is in O(g(n)) if L = c where c is some constant then
f is in Theta(g(n)) if L = inf then f is in Omega(g(n))
What is the definition of O(g(n))?
O(g(n)) implies that there are positive constants m and n_0 for which
0 <= f(n) <= m*g(n) for n >= n_0
How do you implement a stack?
Page 148
How do you implement a queue?
Page 150
How do you implement a bag?
Page 154
How do you make something iterable?
Page 154
How do you implement selection sort?
Page 248
How do you trace selection sort?
Page 249
How do you implement insertion sort?
Page 250
How do you trace insertion sort?
Page 251
