Worst-case, Amortized & Expected Running Times

There are three running times we expect in dealing with data structures: worst-case, amortize and expected. These describe about the time that is used up when we are trying to access data structures with algorithms. Let’s describe what these are.

Worst‐case

The strongest type of running time guarantee; i.e., if an algorithm has a worst‐case running time of 𝑇(𝑛), then any of the operations in the algorithm will never take longer than 𝑇(𝑛). This means that we get the maximum time of T(n) of an algorithm.

Amortized

If an algorithm has an amortized running time of 𝑇(𝑛), this means that the cost of a typical run of this algorithm is about 𝑇(𝑛). Some runs might take longer than 𝑇(𝑛), but with more runs of the algorithm it averages out to 𝑇(𝑛). You can think of this as the “average” time it takes for an algorithm to complete its task. The time it takes to perform an operation is averaged with all the possible operations.

Expected

If an algorithm has an expected running time of 𝑇(𝑛), it means the running time involves a random variable. This is due to random choices made by the algorithm. All we can say is that the expected value of the running time of the algorithm is at most 𝑇(𝑛). That is, it is most likely to be 𝑇(𝑛). This means that the time took for the algorithm to run is close to the expected 𝑇(𝑛).

To understand further, let’s give an example.

Example Case

We are to input a number and find that number in the array given. Suppose we have this array of 8 elements, and we will sort out this array using linear search- meaning we will go through the array, left to right and check if the number we inputted is in the array or not.

Code used:

array_example = [4, 9, 5, 1, 6, 2, 8, -1]


number = int(input("What is the number? "))

def linear_search(lst):
  for i in lst:
    if i == number:
      return "The number is found!"
    
    print(i) # Here we can see what numbers we went through

  return "The number is not found :("

print(linear_search(array_example))

After every iteration in going through the array, we’re going to print that element so that we’ll know that we went through that element.

Worst-case

For worst-case scenario, we take the element -1 at index 7 – the last index. We would have to go through indices 0 to 6 before we get to index 7. This is the maximum time it would take for this algorithm to complete. We don’t get anymore time more than this maximum because we have exhausted the elements in the array.

Also, what if we will search for something that is not in the given array? This would have to still have to go through all the elements in the array before returning if the number is found or not. It went through indices 0 to 7, but since the number is not in the array, the function would just return “The number is not found :(“

Amortized

For amortized, since it’s just the average time it takes for an algorithm to run, we just take all the possible inputs, which are the elements of the array and maybe one or two that aren’t in the array. We take running time T(n) of all the possible inputs and then we divided it by the number of items. This will average to T(n).

Note: With the equation above, we have 8 possible inputs since there are 8 elements in the array, and 1 input that isn’t in the array – a total of 9 inputs.

Expected

For expected, we just take a random variable. In this example, we’ll check if the element 8 is in the array. Knowing that this element is found at index 6, this is expected that this will take longer time than if we’ll check if element 9 at index 1 exists.

Also, if we’ll look if the element 4 exist in the array, knowing it’s at index 0, it’s a lot faster than if we’ll look for element 2 at index 5. Below, we didn’t have to print any number since we returned the element before we got to print it (check code).