Worst Case vs Best Case

Many times we are only concerned with the worst possible case of an algorithm, but in an interview setting its important to keep in mind that worst case and best case scenarios may be completely different Big-O times. For example, consider the following function:

def matcher(lst,match):

    '''

    Given a list lst, return a boolean indicating if match item is in the list

    '''

    for item in lst:

        if item == match:

            return True

    return False

> lst =[1,2,3,4,5,6,7,8]

matcher(lst,1)

False

Note that in the first scenario, the best case was actually O(1), since the match was found at the first element. In the case where there is no match, every element must be checked, this results in a worst case time of O(n). Later on we will also discuss average case time.

Space Complexity:

Many times we are also concerned with how much memory/space an algorithm uses. The notation of space complexity is the same, but instead of checking the time of operations, we check the size of the allocation of memory.

Let's see a few examples:

def printer(n):

    '''

    Prints "hello world!" n times

    '''

    for x in range(n):

        print('Hello World!')

> printer(10)

Hello World!

Hello World!

Hello World!

Hello World!

Hello World!

Hello World!

Hello World!

Hello World!

Hello World!

Hello World!

Note how we only assign the 'hello world!' variable once, not every time we print. So the algorithm has O(1) space complexity and an O(n) time complexity.

Let's see an example of O(n) space complexity:

def create_list(n):

    new_list = []

    

    for num in range(n):

        new_list.append("new" + str(num))

    

    return new_list

> create_list(10)

['new0',

 'new1',

 'new2',

 'new3',

 'new4',

 'new5',

 'new6',

 'new7',

 'new8',

 'new9']

Note how the size of the new_list object scales with the input n, this shows that it is an O(n) algorithm with regards to space complexity.