Running Time as a Function of Input Size
Explore how to analyze an algorithm's running time in relation to input size, using a practical example. Understand how running times can be expressed as functions involving constants and polynomials, setting the foundation for comparing algorithm efficiency.
We'll cover the following...
We'll cover the following...
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 and its length as inputs, and returns the sum of all the elements in the array.
GetSum returns the sum of elements in the input 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 ...