Extra

Question 1

Best, Average, worst time complexty

Quicksort
Mergesort
Bubble sort

Answer 1

Omega(nlogn), Theta(nlogn), O(n^2)

Omega(nlogn), theta(nlogn), O(nlogn)

Omega(n), theta(n^2), O(n^2)

Question 2

Best, Average, worst time complexty

Insertion sort
Selection sort
Binary

Answer 2

Omega(n), theta(n^2),O(n^2)

Omega(n^2), theta(n^2), O(n^2)

Omega(logn), theta(logn), O(n)

Question 3

Order from best to worst time complexity:

Answer 3

1, logn, n, nlogn, n^2,2^n,n!

Question 4

Theta for:

Array

List

Binary

Hash

Answer 4

All n except for
Add()=1
get()=1

All n except for
Add() =1
Remove() =1

All logn

All constants