CSE 331 - Exam 2 Runtimes

For Binary search what is

• best case, worst case, In practice runtime 

• The space complexity

best case —> O(1)

worst case —> O(log n)

in practice —> O(log n)

space complexity —> Iterative → O(1)

__________________Recursive → O(log n)

For Merge Sort what is

• best case, worst case, In practice runtime 

• The space complexity

best —> O(n log n)

worst —> O(n log n)

in practice —> O(n log n)

space —> O(n)

Is merge sort stable, in place?

stable —> yes

in place —> no

For linear search what is

• best case, worst case, In practice runtime 

• The space complexity

best —> O(1)

worst —> O(n)

in practice —> O(n)

space —> O(1)

For Fibonacci what is its runtime

O(2^n)

For Quick Sort what is

• best case, worst case, In practice runtime 

• The space complexity

best —> O(n log n)

worst —> O(n²)

in practice —> O(n log n)

space —> O(log n)

Is Quick Sort stable, in place?

stable —> no

in place —> yes

For Insertion Sort what is

• best case, worst case, In practice runtime 

• The space complexity

best —> O(n)

worst —> O(n²)

in practice —> O(n²)

space —> O(1)

Is Insertion Sort stable? In place?

yes and yes

For Selection Sort what is

• best case, worst case, In practice runtime 

• The space complexity

best —> O(n²)

worst —> O(n²)

in practice —> O(n²)

space —> O(1)

Is Selection Sort stable? In place?

stable —> no

in place —> yes

What is Bubble Sort

1. Start at the beginning of the list.

2. Compare the first two numbers.

3. If the first is bigger, swap them.

4. Move to the next pair and do the same.

5. Keep going until you reach the end — the biggest number has now “bubbled up” to the last spot.

6. Repeat this process for the rest of the list, but stop one earlier each time (since the biggest ones are already at the end).

7. Keep going until no swaps are needed — the list is sorted.

For Bubble Sort what is

• best case, worst case, In practice runtime 

• The space complexity

best —> O(n)
worst —> O(n²)
in practice —> O(n²)

Is Bubble Sort stable? In place?

yes and yes

What is heap Sort

For Heap Sort what is

• best case, worst case, In practice runtime 

• The space complexity

O(n log n)

Is Heap Sort stable? In place?

stable —> no
in place —> yes

For Radix Sort what is

• best case, worst case, In practice runtime 

• The space complexity

best —> O(n)

worst —> O(n)

in practice —> O(n)

Is Radix Sort stable? In place?

stable —> yes
in place —> no