Running Time as a Function of Input Size

A toy example

Let’s look at a toy example to help distill our notion of running time. We define a function GetSum that takes an array $A$ and its length $n$ as inputs, and returns the sum of all the elements in the array.

Viewing the running time as a function

Let’s look at the running time of each instruction in the above algorithm.

Note that each $C_i$ in the table below (where $i\in\{1,2,3,4\}$) represents some constant specific to the underlying machine. We don’t know its numeric value, but we do know it is some constant number.

Line number	Time taken to execute
2	$C_1$
3	$C_2 (n+1)$

...