CSCI exam II Revised

log(n) =0(n)

T

n=0(log n)

F

log²(n) =0(n)

T

n = O(log2n)

F

log(n) = Ω (n)

F

n = Ω (log n)

T

5n3+ 7n + 13 = O(n5)

T

5n3 + 7n + 13 = Ω (n³)

F

5n3 + 7n + 13 = 0(n)

T

log(n!) = θ(n log(n))

T

n = O(log n)

F

2n= Ω (n!)

F

What is the big-Oh run time of Merge Sort on n items?

O (n log n)

What is the big-Oh run time of Heap Sort on n items?

O (n log n)

What is the worst-case big-Oh run time of Quick Sort of n items?

O (n^2)

What is the worst-case big-Oh run time of Selection Sort on n items?

O (n^2)

What is the big-Omega lower bound for comparison based sorting ofn items?

Omega (n log n)

What is the worst case big-Oh run time to insert 1 item into an AVL-tree that contains n
Items?

O(log n)

What is the worst-case big-Oh run time to insert 1 item into a normal binary search tree
that contains n items?

O(n)

What is the worst case big-Oh run time to insert 1 item into a min-heap?

O(log n)

What is the worst case big-Oh run time to remove the minimum value from a min-heap?

O(n)

What is the worst case big-Oh run time of Binary Search on an n item sorted list?

O(log n)

What is the worst case big-Oh run time to insert 1 item into a min-heap?

O(log n)

What is the worst case big-Oh run time to remove the minimum value from a min-heap?

O(log n)

What is the run time of breadth-first search (in terms of V| and |E|)?

O([V+ E)

What is the run time of Dijkstra's algorithm (in terms of [V| and [E) with a minheap
Implementation?

O (([V| + |E|) log |V)

What is the run time of Bellman-Ford algorithm (in terms of [V| and|E|)?

O([V||E)

17n³ + 4n + 5

O(n5)

17n + 4n + 5

θ (n³)

17n³ + 4n + 5

Ω (n)

log(n)

0 (n1/2)

n1/2

Ω (log²n)