Complexity and Data Structures
Daniel Archambault
CS-115: Complexity
1
Previously in CS-115
a
Graphs connect the world!
CS-115: Complexity
2
Previously in CS-115
What differentiates a graph from a tree?
CS-115: Complexity
3
Previously in CS-115
What differentiates a graph from a tree? What is a directed graph?
CS-115: Complexity
3
Previously in CS-115
What differentiates a graph from a tree? What is a directed graph?
What is an undirected graph?
CS-115: Complexity
3
Previously in CS-115
What differentiates a graph from a tree? What is a directed graph?
What is an undirected graph?
What is degree?
CS-115: Complexity
3
Previously in CS-115
What differentiates a graph from a tree? What is a directed graph?
What is an undirected graph?
What is degree?
What are two graph data structures that implement the ADT?
CS-115: Complexity
3
Previously in CS-115
What differentiates a graph from a tree? What is a directed graph?
What is an undirected graph?
What is degree?
What are two graph data structures that implement the ADT? What are advantages/disadvantages?
CS-115: Complexity
3
Previously in CS-115
Complexity of algorithms? What about data structures?
Complexity and Data Structures
CS-115: Complexity
4
Complexity, Data Structures, and Sorting
Complexity tries to quantify how fast or big something is
given an input size of n how long could this take?
given an input size of n how much memory/space do we need?
We use n as the input size because it’s variable
With big n, sometimes a lot of time and space is required!
In this lecture, we look at worst case (how bad it can get) and average case complexity.
CS-115: Complexity
5
Rules of Complexity
In complexity, we worry only about the largest exponent We ignore all constant values and lower exponents
2n3 +32n2 +4 is O(n3)
Why can we do this? As n becomes really large, other terms don’t matter so much.
CS-115: Complexity
6
Space Complexity
You have already done time complexity? Think sorting…
Well, you can use the same tool to talk about how much space something takes in memory.
Given an input size of n, it’s possible for it to take O(n2) space Important for data structures
time complexity for the operations on the data
space complexity for the data itself
CS-115: Complexity
7
Warning!
In this lecture we estimate complexity
We are providing estimates not proofs Complexity theory is hard and involves proofs
particular algorithm has performance…
any algorithm for a problem will have performance…
Our arguments are not proofs, but estimates In second year, you will do rigourous proofs.
CS-115: Complexity
8
Array Complexity
int[] a = new int [n];
Insertion complexity?
CS-115: Complexity
9
Array Complexity
int[] a = new int [n];
Insertion complexity? O(n) Access complexity?
CS-115: Complexity
9
Array Complexity
int[] a = new int [n];
Insertion complexity? O(n) Access complexity? O(1) Space complexity?
CS-115: Complexity
9
Array Complexity
int[] a = new int [n];
Insertion complexity? O(n) Access complexity? O(1)
Space complexity? O(n)… usually
CS-115: Complexity
9
Linked List Complexity
head
next element
Obj.
tail
next next null element element
Obj. Obj.
Insertion complexity (if location known)?
CS-115: Complexity
10
Linked List Complexity
head
next next element element
tail
next null element
Obj. Obj. Obj.
Insertion complexity (if location known)? O(1) Access complexity?
CS-115: Complexity
10
Linked List Complexity
tail
next element
next element
next element
head
Obj.
Insertion complexity (if location known)? O(1) Access complexity? O(n)
Space complexity?
null
Obj.
Obj.
CS-115: Complexity
10
Linked List Complexity
tail
next element
next element
next element
head
Obj.
Insertion complexity (if location known)? O(1) Access complexity? O(n)
Space complexity? O(n)
null
Obj.
Obj.
CS-115: Complexity
10
Queue
dbef
c
isEmpty complexity?
CS-115: Complexity
11
Queue
dbef
c
isEmpty complexity? O(1) enqueue/dequeue complexity?
CS-115: Complexity
11
Queue
dbef
c
isEmpty complexity? O(1) enqueue/dequeue complexity? O(1) peek complexity?
CS-115: Complexity
11
Queue
d
b
e
f
c
isEmpty complexity? O(1) enqueue/dequeue complexity? O(1) peek complexity? O(1)
Space complexity?
CS-115: Complexity
11
Queue
d
b
e
f
c
isEmpty complexity? O(1) enqueue/dequeue complexity? O(1) peek complexity? O(1)
Space complexity? O(n)
CS-115: Complexity
11
Stack
12 51 17
isEmpty complexity?
CS-115: Complexity
12
Stack
12 51 17
isEmpty complexity? O(1) push/pop complexity?
CS-115: Complexity
12
Stack
12 51 17
isEmpty complexity? O(1) push/pop complexity? O(1) peek complexity?
CS-115: Complexity
12
Stack
12
51
17
isEmpty complexity? O(1) push/pop complexity? O(1) peek complexity? O(1) Space complexity?
CS-115: Complexity
12
Stack
12
51
17
isEmpty complexity? O(1) push/pop complexity? O(1) peek complexity? O(1) Space complexity? O(n)
CS-115: Complexity
12
Binary Search Tree
Find a element?
CS-115: Complexity
13
Binary Search Tree
Find a element? can be O(n) but usually O(lg(n))
a balanced binary tree has maximum height of O(lg(n))
O(lg(n)) – log base 2 of n
Print out in alphabetical order?
CS-115: Complexity
13
Binary Search Tree
Find a element? can be O(n) but usually O(lg(n))
a balanced binary tree has maximum height of O(lg(n))
O(lg(n)) – log base 2 of n
Print out in alphabetical order? O(n) Space complexity?
CS-115: Complexity
13
Binary Search Tree
Find a element? can be O(n) but usually O(lg(n))
a balanced binary tree has maximum height of O(lg(n))
O(lg(n)) – log base 2 of n
Print out in alphabetical order? O(n) Space complexity? O(n)
CS-115: Complexity
13
Hash Maps
Hash Function
”Dan!”
”Swansea!” ”Oh No!”
0
3 1
1 2 3
3
4
(”Swansea!”, 33)
(”Dan!, 27)
(”Oh No!”, 8)
Find a element?
CS-115: Complexity
14
Hash Maps
Hash Function
”Dan!”
”Swansea!” ”Oh No!”
0
3 1
1 2 3
3
4
(”Swansea!”, 33)
(”Dan!, 27)
(”Oh No!”, 8)
Find a element? assume good hash function O(1) Insert an element?
CS-115: Complexity
14
Hash Maps
Hash Function
”Dan!”
”Swansea!” ”Oh No!”
0
3 1
1 2
3
3
4
(”Swansea!”, 33)
(”Dan!, 27)
(”Oh No!”, 8)
Find a element? assume good hash function O(1) Insert an element? assume good hash function O(1) Space complexity?
CS-115: Complexity
14
Hash Maps
Hash Function
”Dan!”
”Swansea!” ”Oh No!”
0
3 1
1 2
3
3
4
(”Swansea!”, 33)
(”Dan!, 27)
(”Oh No!”, 8)
Find a element? assume good hash function O(1) Insert an element? assume good hash function O(1) Space complexity? usually O(n)
CS-115: Complexity
14
Heaps and Priority Queues
27
27 8422
Look at the top?
10
CS-115: Complexity
15
Heaps and Priority Queues
27
27 8422
Look at the top? O(1) Insert an element?
10
CS-115: Complexity
15
Heaps and Priority Queues
27
27 8422
Look at the top? O(1) Insert an element? O(lg n) Remove the front/root?
10
CS-115: Complexity
15
Heaps and Priority Queues
27
27 8422
Look at the top? O(1)
Insert an element? O(lg n) Remove the front/root? O(lg n) Space complexity?
10
CS-115: Complexity
15
Heaps and Priority Queues
27
27 8422
Look at the top? O(1)
Insert an element? O(lg n) Remove the front/root? O(lg n) Space complexity? usually O(n)
10
CS-115: Complexity
15
Graphs: Matrix
Node[] nodes; //list of n nodes (made by
constructor)
Edge[][] matrix; //nxn matrix specified by
constructor
Look up or remove an edge (given its 2 nodes)?
CS-115: Complexity
16
Graphs: Matrix
Node[] nodes; //list of n nodes (made by
constructor)
Edge[][] matrix; //nxn matrix specified by
constructor
Look up or remove an edge (given its 2 nodes)? O(1) Look up or remove a node?
CS-115: Complexity
16
Graphs: Matrix
Node[] nodes; //list of n nodes (made by
constructor)
Edge[][] matrix; //nxn matrix specified by
constructor
Look up or remove an edge (given its 2 nodes)? O(1) Look up or remove a node? O(n)
Space complexity?
CS-115: Complexity
16
Graphs: Matrix
Node[] nodes; //list of n nodes (made by
constructor)
Edge[][] matrix; //nxn matrix specified by
constructor
Look up or remove an edge (given its 2 nodes)? O(1) Look up or remove a node? O(n)
Space complexity? O(n2)
CS-115: Complexity
16
Graphs: Linked
public class Graph {
Node[] nodes;
…. }
public class Node {
Edge[] edgeList; //list of degree nodes
}
Look up or remove an edge?
CS-115: Complexity
17
Graphs: Linked
public class Graph {
Node[] nodes;
…. }
public class Node {
Edge[] edgeList; //list of degree nodes
}
Look up or remove an edge? O(n) Look up or remove an node?
CS-115: Complexity
17
Graphs: Linked
public class Graph {
Node[] nodes;
…. }
public class Node {
Edge[] edgeList; //list of degree nodes
}
Look up or remove an edge? O(n) Look up or remove an node? O(n) Space complexity?
CS-115: Complexity
17
Graphs: Linked
public class Graph {
Node[] nodes;
…. }
public class Node {
Edge[] edgeList; //list of degree nodes
}
Look up or remove an edge? O(n) Look up or remove an node? O(n) Space complexity? O(n + e)
CS-115: Complexity
17
Complexity of Comparison-Based Sorting
All sorting algorithms currently are comparison based
general sorting algorithms that involves knowing nothing about data
We know that there are algorithms that take O(n lg n) comparisons But, surely, there are faster algorithms, Dan?
CS-115: Complexity
18
Complexity of Comparison-Based Sorting
All sorting algorithms currently are comparison based
general sorting algorithms that involves knowing nothing about data
We know that there are algorithms that take O(n lg n) comparisons But, surely, there are faster algorithms, Dan?
For comparison-based sorts, no.
mathematical proof says you need at least Ω(n lg n) comparisons
proof is hard, but we can do it for fun sometime…
However, if you know something about the data, you can do better!
CS-115: Complexity
18
Bucket Sort: O(n)
If you know that your data can be easily divided into b buckets, you can use bucket sort which is O(n).
The algorithm:
Create an array of b elements. Each stores an array or linked list.
Traverse all n unsorted elements, throwing each into their correct
bucket.
Assuming each bucket has a small number of elements, sort by any
means.
If any particular bucket ends up with n elements it is O(n2) Bucket sort is really useful, especially with hashmaps
I’ve personally used this strategy many times.
CS-115: Complexity
19
Radix Sort: O(n)
If you know that each element of your data has a key of b digits, you can use radix sort which is O(bn).
Algorithm:
start with the least significant digit and apply bucket sort
loop through all digits up to the greatest digit
Assumption is good bucket sorts and small number lengths. What to do with non-integer keys…
Still much debate about its complexity
CS-115: Complexity
20