Time Complexity

Viewing the time it takes to run an algorithm. Input size depends on type of object:

• String: number of characters
• List: number of elements
• Graph: number of vertices or number of edges

Runtime

Running time $T(n)$ of an algorithm for input size $n$ is number of primitive operations/steps executed

• Steps are machine independent

Complexity Types

• Best-case
• Average-case
• Worst-case

Calculating Runtime Complexity

Total running time = $\text{machine dependent cost}\ast \text{num of times}$