6.00.1x Week 5 (Incomplete)


How much time it takes for our program to run.

The function iterates elements in list L, if the element is equals to x, it returns true. This function continues to iterate until x is found, or if not found, returns false.

There are two extreme cases here, if x happens to be near the front of list L, it will be found immediately, taking less time. If however, the worst case, x is not in list L, it will take time to iterate over each element, taking more time. Different x input requires different running time. So to implement the measurement of efficiency in terms of basic steps, we introduce a concept called best case and worst case.

Best case: minimum amount of time to run the program
For linear search – constant, independent of input size.

Worst case: maximum amount of time to run the program
For linear search – size of list.

Average case: average amount of time to run the program

Measuring time in terms of basic steps executed

Each basic step such as assignment, comparison, arithmetic operations, and accessing object in memory is assumed to take constant time.

In this example, for each loop, we need to assign e to each element of list L (in for e in L) and check if e is equals to x (in if e == x). In the best case, the list L is empty, so we only execute one step (return False). The running time is 1.

In the worst case, x is not in list L, so we go through the loop n times, where n is the number of elements in list. For each loop, we execute two steps, so total of 2n steps. And finally, we execute the (return False) step, making the running time of worst case 2n+1.

Leave a Reply