ICS4U – Python Algorithm Efficiency

ICS4U Grade 12 Computer Science ICS4U – Python Algorithm Efficiency

ICS4U Learning Goals

In this ICS4U Grade 12 Computer Science lesson you will be learning how to

Differentiate between Time and Space Complexity for an algorithm
Write Big O notation for search algorithms
Write Big O notation for sorting algorithms

Run Time Analysis

Back in the recursion lesson you were introduced to the timeit library in python that is a pretty straightforward way to calculate how long a certain piece of code takes to execute.

				
					
import timeit

start = timeit.default_timer()

#Code to find the running time for

end = timeit.default_timer()

#Find the time it took the code to run
time = end - start

The time is recorded in seconds. Since the code blocks you are looking at likely execute pretty quickly, it might be better to look at a different unit such as milliseconds, microseconds, or nanoseconds.

To Convert:

milliseconds -> multiply by 10^3
microseconds -> multiply by 10^6
nanoseconds -> multiply by 10^9

				
					
import timeit

start = timeit.default_timer()

#Code to find the running time for

end = timeit.default_timer()

#Find the time it took the code to run
time = end - start
timeMilli = time * 10**3
timeMicro = time * 10**6
timeNano = time * 10**9

Feel free to round the answers as well if it makes it easier to analyze. Since 20 microseconds and 20.1 microseconds and 20.2 microseconds aren’t that different.

Things to keep in mind

The run time is going to be affected by a lot of different factors that have nothing to do with how “efficient” your code is. Running the same code on different machines with different processors will produce different run times. Even running the code on the same machine will produce different run times depending on what else the processor is doing at the time. So just using raw run times to do comparisons, is not always the best approach. The data being analyzed can also have a significant effect on the run time of a particular algorithm.

So deciding on the “efficiency” of a particular algorithm just using raw run times isn’t the greatest idea. But it can definitely give you an initial sense of what algorithm might be more efficient in terms of execution time.

Example - Comparing Bubble Sort to Quick Sort

				
					import random
import timeit

#Quick Sort Functions -> Fill in code yourself
def quickSort(a):
def sortPartition(a,0,len(a)-1)
def bubbleSort(a)

#Function to generate random list
def genRandomList(n,min,max):

	a = []
	for i in range(0,n):
		a.append(random.randint(min,max))

	return a

#Copy an existing list into a new list
def copyList(a):

    newList = []
    for i in range(0,len(a)):
        newList.append(a[i])
    return newList

def main():

	#Generate a random list with 5000 elements between 0 and 20000
	originalList = genRandomList(5000,0,20000)

	#Need copies of the list to give to all the sorting functions because sort functions modifies original list
	blist = copyList(originalList)
	qlist = copyList(originalList)

	#Time bubble sort on the list
	start = timeit.default_timer()
	bubbleSort(blist)
	end = timeit.default_timer()
	bubbleTimeMicro = int((end-start)*10**6)
	print("Bubble Time:", bubbleTimeMicro)

	#Time Quick sort on the list
	start = timeit.default_timer()
	bubbleSort(blist)
	end = timeit.default_timer()
	quickTimeMicro = int((end - start) * 10 ** 6)
	print("Quick Time:", quickTimeMicro)


main()

Some notes on the code:

I wanted to sort on the exact same list for both algorithms and since my sort functions modify the original lists, I need to make copies of the original list first.
You can’ t just use = to make a copy of a list if you are planning on changing the list because using = will just point both lists to the same memory location. Changing the one list will change the other.

Conclusions:

If you run this code several times, you will see the execution times change slightly each time.
Its pretty clear that its likely the quick sort is running much faster then the bubble sort under these circumstances

Options to deal with variability

You could run the algorithm multiple times (Say 100 times) and then take an average of those time values, to get a more complete picture of the run time on a particular machine.

Time and Space Complexity

Its not always very practical to check the run time of an algorithm to test its efficiency. Especially if we need to take an averaging approach to remove some variability. Instead its easier to use a theoretical approach.

There are two types of analysis we could do

Time Complexity Analysis
- The amount of time taken by an algorithm to run as a function of the length of the input.
Space Complexity Analysis
- The amount of memory required to solve a problem using an algorithm

Big O Notation

This course provides a brief introduction to Time Complexity Analysis, often referred to as Big O Notation. Big O Notation aims to provide a way to analyze an algorithm as it scales with larger amounts of data.

Time Complexity For Searching Algorithms

Sequential (Linear) Search

Best Case Complexity

The best case occurs when the element we are finding is at the first position of the list.
It has a time complexity of O(1)

Average Case Complexity

The average case occurs if the target is randomly located somewhere inside the list.
It has a time complexity of O(n)

Worst Case Complexity

The worst case occurs when the target we are looking for is at the end of the list or if the target being searched for is not in the list at all.
It has a time complexity of O(n)

Binary Search

Best Case Complexity

The best case occurs when the element to search is found in the first comparison….when the first middle element itself is the target being searched for.
It has a time complexity of O(1)

Average Case Complexity

The average case occurs if the target is randomly located somewhere inside the list.
It has a time complexity of O(log(n))

Worst Case Complexity

The worst case occurs when we have to keep reducing the search space until the very end where there is only one element left
It has a time complexity of O(log(n))

Time Complexity For Basic Sorting Algorithms

Selection Sort

Best Case Complexity

The best case occurs when there is no sorting required….. the list is already sorted.
It has a time complexity of O(n^2)

Average Case Complexity

The average case occurs if the elements in the list are in a randomized non sorted order.
It has a time complexity of O(n^2)

Worst Case Complexity

The worst case occurs when we have the elements in reverse order then what they need to be sorted. So if you wanted to sort in ascending order, the worst case is they are already sorted in descending order
It has a time complexity of O(n^2)

Bubble Sort

Best Case Complexity

The best case occurs when there is no sorting required….. the list is already sorted.
It has a time complexity of O(n)

Average Case Complexity

The average case occurs if the elements in the list are in a randomized non sorted order.
It has a time complexity of O(n^2)

Worst Case Complexity

The worst case occurs when we have the elements in reverse order then what they need to be sorted. So if you wanted to sort in ascending order, the worst case is they are already sorted in descending order
It has a time complexity of O(n^2)

Insertion Sort

Best Case Complexity

The best case occurs when there is no sorting required….. the list is already sorted.
It has a time complexity of O(n)

Average Case Complexity

The average case occurs if the elements in the list are in a randomized non sorted order.
It has a time complexity of O(n^2)

Worst Case Complexity

The worst case occurs when we have the elements in reverse order then what they need to be sorted. So if you wanted to sort in ascending order, the worst case is they are already sorted in descending order
It has a time complexity of O(n^2)

Time Complexity For Quick Sort Algorithm

Quick Sort

Best Case Complexity

The best case occurs when the pivot element is the middle element or near to the middle element.
It has a time complexity of O(n*log(n))

Average Case Complexity

The average case occurs if the elements in the list are in a randomized non sorted order.
It has a time complexity of O(n*log(n))

Worst Case Complexity

The worst case occurs when the pivot element is either greatest or smallest element.
If the pivot is always the last element, the worst case would be when the list is already sorted in either ascending or descending order.
It has a time complexity of O(n^2)

Python Built in Sort

In general, you can assume the time complexity of pythons built in sorting function is O(n*log(n))

Previous Lesson

Back to Course

Next Lesson