Measure execution time

• Needs to run the program
• Dependent on hardware, programming language, other running processes…

Something more abstract: complexity

• Number of operations as a function of the input size $n$
• We use the $O(\cdot)$ notation, e.g., $O(n)$, $O(n^2)$, $O(n!)$

$\rightarrow$ Independent of hardware, programming language…

$\rightarrow$ Does not need the program to be run

• Examples – DFS/DFS: $O(|E|)$ ; Dijkstra: $O(|E| + |V| \cdot log(|V|))$

The complexity of a problem is the minimum complexity of the algorithms solving the problem

• Equivalence classes between algorithms and problems
• Dijkstra, BFS, DFS are polynomial algorithms for finding paths (problems of class P)
• Some problems cannot be solved with a known polynomial algorithm, e.g, the traveling salesman problem (NP-complete problem)

Find the shortest path that goes through all locations

Find the shortest route that goes through all vertices of a complete graph

• Note – This boils down to performing a DFS per branch

• Number of skipped branches depend on quality of the first explored ones
• This doesn’t change the (worst-case) complexity

• Algorithms can be compared according to their complexity

• Problem complexity is determined by the best algorithm to solve it

• There are some very hard to solve problems, like TSP

• Such problems can only be solved by testing all possible solutions