Algorithm and data structure time complexity

Question 1

Insertion sort

Answer 1

best: Ω(N)
avg: Θ(N^2)
worst: O(N^2)

Space complexity: O(1)

Question 2

Merge sort

Answer 2

best/avg/worst: Θ(N log2 N)

space complexity: O(N)

Question 3

Quick sort

Answer 3

best: Ω(N log2 N)
avg: Θ(N log2 N)
worst: O(N^2)

Space complexity: O(log N)

Quicksort worst case: only remove one element from sorted or reverse-sorted data, will only remove one element from data with many duplicates; leads to incremental execution resembling insertion sort: N levels of recursion, N - i elements to partition at level i
Worst case Θ(N^2)

Best case: partitioning is balanced, subproblems no larger than N/2
Θ(N log2 N)

Random pivot selection alters the worst case to become matter of chance for all inputs
possibility of choosing worst pivot in every call gets stalling as N increases
average case Θ(N log2 N) “expected”

Space complexity: O(log N)

Question 4

Heap sort

Answer 4

Best/avg/worst: Θ(Nlog2N)

Space complexity: O(1) possible, but I believe method we learned in class was O(N)

Question 5

Array

Answer 5

Search/insert/delete: Θ(N)
acces: Θ(1)

Space complexity: O(N)

Question 6

Sorted array

Answer 6

Search: O(log N)
Insert/Delete: O(N)

Space complexity: O(N) (?)

Question 7

Linked list

Answer 7

Search/access: O(N)
Insert/delete: O(1)

Space complexity: O(N)

Question 8

Stack

Answer 8

Search/access: O(N)
Insert/delete: O(1)
(average and worst)

Space complexity: O(N)

Question 9

Hash table

Answer 9

Average:
Search/insert/delete: Θ(1)

Worst case:
Search/insert/delete: Θ(N)

if m proportional to N
chaining: get is amortized constant, put is constant ; expected time complexity is Θ(N/m) because of SUHA, worst case O(N)

uniform hashing - expected number of keys compared when inserting an object depends on the load factor N/m
probing: put and get amortized constant under uniform hashing

Space complexity: O(N)

Question 10

Binary search tree

Answer 10

Avg search, insert, delete: Θ(log2 N)
Worst search, insert, delete: O(N)

Space complexity: O(N)

Question 11

Red-Black tree

Answer 11

Search/access/insert/delete: O(log2 N)
(average and worst)

Space complexity: O(N)

Question 12

BFS

Answer 12

O(|V + E|)

space complexity: O(|V|) (worst case hold all nodes in queue)

Question 13

DFS

Answer 13

O(|V + E|)

space complexity: height of tree or if using queue get O(|V|)

Question 14

Prim’s

Answer 14

O(E log2 V) assuming queue is implemented as a binary heap
queue operations determine the running time
all edges added to queue
worst case: all edges removed from queue
E log2 E = O(E log2 V) as in Kruskal’s

Question 15

Bellman-Ford

Answer 15

O(V*E)

Question 16

Dijkstra’s

Answer 16

O(E log2 V)

use binary-heap-based priority queue = all operations run in O(log2 V)
one iteration through the graph vertices
each edge relaxed once, aggregate of |E|

Question 17

Priority queue

Answer 17

adding and removing O(log2 N) ie limited by height of tree

Space complexity: O(N)

Question 18

Binary search

Answer 18

Θ(log2 N)

Question 19

Kruskal’s

Answer 19

O(E log2 V)

disjoint set data structure is O(log|V|) for all operations
sorting edges is O(E log2 E)

E < V^2, so log2 E < 2 log2 V and E log2 E = O(E log2 V)
Overall time: O(E log2 V)

Question 20

Queue

Answer 20

Search/access: Θ(N)
Insert/delete: Θ(1)

Space complexity: O(N)