Time Complexity Fun

What is worst case run time for quick sort?

• O(nlogn)
• O(n)
• O(log n)

• O(n^2)

What is best case run time for insertion sort?

• O(log n)
• O(n^2)
• O(n)
• O(1)

What is worst case runtime for merge sort?

• O(log n)
• O(n)
• O(n log n)
• O(n^2)

What is best case run time for quick sort?

• O(n log n)
• O(log n)
• O(n^2)
• O(n)

What is worst case runtime for insertion sort?

• O(n^2)
• O(log n)
• O(1)
• O(n)

What is best case runtime for merge sort?

• O(n^2)
• O(n log n)
• O(n)
• O(log n)

log(n) = θ(n)

• True

• False

n = O(log n)

• True
• False

2^n =  Ω (n)

• True
• False

n =  Ω (log^2(n) )

• True

• False