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 ...