Miscellaneous Topics

19. Miscellaneous Topics#

This notebook covers three topics. First, we look at the runtime costs of algorithms followed by a discussion of criteris used for selecting data structures and how different operations can affect run time costs within those data structures. Finally, the notebook presents a summary of references within Python.

19.1. Analysis of Algorithms#

As mentioned at the start of these notebooks, one of the fundamentals problems within computer science concerns the efficiency of a particular solution (i.e., algorithm) to a class of problems. Formally, this field is called “analysis of algorithms” and seeks to find the amount of resources (typically time and space) needed to execute the solution.

Two of the primary tools use in this analysis are the the RAM model of computation and the asymptotic analysis of computational complexity (i.e., big “O” notation).[1]

19.1.1. RAM Model of Computation#

The Random Access Machine(RAM) model provides a hypothetical computer that allows us to perform machine independent analysis of algorithms.[1] In this model, we have a simplified computer in which -

Each simple operation (statement, arithmetic operation, assignment, if, function call) takes exactly one time step
Loops and functions are composed of many single step operations. Their time steps depend upon the number of loop iterations of the specific steps within the function.
Each memory access takes one time step. The amount of memory is virtually unlimited.

Under this model, run time is determined by counting the number of time steps a solution takes for a given problem instance. For instance, given the below code

def print_list(items):
    for item in items:
        print(item)

print_list(["one","two","three"])

has a run time cost of 4. One for the function call, and then three for looping through the list. It could also be considered to have a run time cost of 7 as the last statement requires iterating through items to create the list and then function call itself. However, as we will see next, that difference becomes immaterial.

19.1.2. Asymptotic Analysis and Big Oh Notation#

The above example demonstrates the cost for a specific instance of inputs. However, we also need to look at the costs against all possible instances (inputs). As we look as these costs, we can look at this over the worst-case, best-case, and average-case runtimes of the column. For our simple example, these will all be the same. However, as the below figure from The Algorithm Design Manual demonstrates, they can depending upon the algorithm and the specific instances of inputs.[1]

In our example, the runtime is directly correlated with the size of the list, \(n\). We could define a formula for the exact cost as \(2n+1\).

However, dealing with that exact cost can become impractical. Given a worst-case cost formula such as \(T(n) = 345n^2 + 30n + 4\), the specific amount provides little value beyond the fact that time grows quadratically with \(n\).[1] As such, we adopt Big Oh notation in which we ignore details and focus how the cost grows in relationship to \(n\) representing the size of inputs. Big Oh allows us to ignore constants and small factors of \(n\) in the formula.

Formally, \(f(n) = O(g(n)) \) means \(c \cdot g(n)\) is an upper bound on \(f(n)\). Thus, there exists some constant \(c\) such that \(f(n) \lt c \cdot g(n)\) for every large enough \(n\).[1] This could be read a \(n \rightarrow \infty\).

Realize that under Big Oh notatation, we discard constants. So \(f(n) = 0.001n^2\) and \(g(n) = 1000n^2\) are treated equally, despite one allows being largely by several orders of magnitude. Where this makes more intuitive sense is when we look at the growth rates over several different classes of Big Oh.

\(n\)	1	log \(n\)	\(n\) log \(n\)	\(n^2 \)	\(2^n\)	\(n!\)
1	1	0	0	1	2	1
10	1	1	10	100	1,024	3,628,800
20	1	1	26	400	1,048,576	2,432,902,008,176,640,000
30	1	1	44	900	1,073,741,824	2.65253E+32
100	1	2	200	10,000	1.26765E+30	9.3326E+157
1,000	1	3	3,000	1,000,000	1.0715E+301	…
10,000	1	4	40,000	100,000,000	…	…
100,000	1	5	500,000	10,000,000,000	…	…
1,000,000	1	6	6,000,000	1,000,000,000,000	…	…

As you can see, for different classes, the run time cost can increase quite dramatically even with small values of \(n\). \(n!\) cost often occurs when we need to look at all possible combinations of \(n\) items such as to determine the optimal path in the traveling person problem. Many of the algorithms in machine learning rely upon matrix multiplication. The non-optimized algorithm for matrix multiplication has a Big Oh of \(O(n^3)\).

19.1.3. Case Study: Sorting#

Sorting is one of the core algorithms in computer science - we are constantly organizing our data in same way - whether alphabetical, by some priority, or some other factor. Over time, researchers have produced a number of different sort algorithms. Most of these algorithms are divided into two classes of run time: \(n^2\) and \(n\) \(log\) \(n\). Obviously, we want to use the faster algorithms. Fortunately, most programming APIs now have sorting routines provided and we no longer have to write custom routines (although we may write custom functions or lambdas to perform unique comparison operations).

Although rarely used outside of classroom settings, bubble sort continues to taught to demonstrate a straightforward approach to ordering data. Bubble sort repeated swaps elements if they are in the wrong order and requires a nested iteration throgh all of the elements.

def bubble_sort(items):
    for i in range(len(items)):                   # Ensure we access each array element
        for j in range(0, len(items) - i - 1):    # loop to compare elements, don't need to check the end
                                                  # as it has been sorted ina previous iteration of i
            if items[j] > items[j + 1]:           # swap if out of order  
                temp = items[j]
                items[j] = items[j+1]
                items[j+1] = temp
            print("inner:",items)
        print(items)                              # see how the larger numbers bubble to the end

data = [19, 5, 6, 3, 17, 1]

bubble_sort(data)
print("\nSorted:",data)

inner: [5, 19, 6, 3, 17, 1]
inner: [5, 6, 19, 3, 17, 1]
inner: [5, 6, 3, 19, 17, 1]
inner: [5, 6, 3, 17, 19, 1]
inner: [5, 6, 3, 17, 1, 19]
[5, 6, 3, 17, 1, 19]
inner: [5, 6, 3, 17, 1, 19]
inner: [5, 3, 6, 17, 1, 19]
inner: [5, 3, 6, 17, 1, 19]
inner: [5, 3, 6, 1, 17, 19]
[5, 3, 6, 1, 17, 19]
inner: [3, 5, 6, 1, 17, 19]
inner: [3, 5, 6, 1, 17, 19]
inner: [3, 5, 1, 6, 17, 19]
[3, 5, 1, 6, 17, 19]
inner: [3, 5, 1, 6, 17, 19]
inner: [3, 1, 5, 6, 17, 19]
[3, 1, 5, 6, 17, 19]
inner: [1, 3, 5, 6, 17, 19]
[1, 3, 5, 6, 17, 19]
[1, 3, 5, 6, 17, 19]

Sorted: [1, 3, 5, 6, 17, 19]

As you can see by counting the resulting output line from the function, the loop executes \(n(n+1)/2\) times. From a Big Oh perspective, this has \(O(n^2)\).

19.2. Choosing a Data Structure#

Choosing a data structure depends both upon what you need to store as well as the operations that you need to perform upon the data.

If you need to track a list of elements and access those elements by position, use a list.

If you need to access an element by a specific value, use a dictionary.

Data structures also have different runtime speeds for various operations. As we perform this analysis, we look at how the runtime cost grows respective to the number of elements in a collection. Two such categories of runtime cost are \(O(n)\), where the cost grows linearly to the number of elements in the list, and \(O(1)\), where the cost is constant.

These speeds are relative and not necessarily exact. The point is to compare the costs of different operations within the same collection type (list, dictionary, etc.) and the same operation in different collection types.

For lists:

Operation	Runtime Cost
Insert at the start of a list	\(O(n)\)
Insert at the end of a list	\(O(1)\)
Remove at the start of a list	\(O(n)\)
Remove at the end of a list	\(O(1)\)
Check if a value exists in the list	\(O(n)\)

To see how this would work from an empirical basis, we can perform some rough timing experiments to test the cost of these operations. Jupyter can assess how long code blocks execute by using a %%timeit instruction at the start of a code cell. With this instruction, we can run the code cell n times and then repeat the process r times. Any changes to existing objects remain from one execution to the subsequent execution.

Time running adding the value “hello” to the start of the list 100,000 times. Repeat five times

%%timeit -r 5 -n 1
l = []
for x in range(0,1000):
    l.append(x)
    
for x in range(0,100000):
    l.insert(0,"hello")
print(len(l))

101000
1.54 s ± 53.3 ms per loop (mean ± std. dev. of 5 runs, 1 loop each)

Now, test adding hello to the end of the list.

%%timeit -r 5 -n 1
l = []
for x in range(0,1000):
    l.append(x)
    
for x in range(0,100000):
    l.append("hello")
print(len(l))

101000
101000
101000
101000
101000
1.25 ms ± 90.4 µs per loop (mean ± std. dev. of 5 runs, 1 loop each)

Inserting a value at the start of the list was approximately three orders of magnitude slower than adding it to the end of the list.

The spend difference is a result of how Python stores lists. Behind the scenes, Python uses an array to store the references. Like a list, arrays hold elements (usually the same type) in a contiguous memory block. The following image was created by the list: ["it","was","the","best","of","times"]

Source: Generated at pythontutor.com

Checking if a value exists is \(O(n)\) as we must iterate through the array to find the value. While, on average, this would take \(n/2\) tries, for this analysis, the cost still grows linearly with the size of the list and, hence, we consider it to be \(O(n)\)

Inserting an element at the start of a list requires the Python interpreter to shift all elements in the backing array to the right by one position. This shift has a runtime cost of \(O(n)\)

In contrast, inserting an element at the end of a list does not require that shift. Instead, the Python interpreter typically allocates a larger array than the number of elements in a list to allow for growth. When this array becomes full, the interpreter allocates an even larger array and copies the current contents into that new array. From a cost analysis perspective, we amortize this action over numerous operations and thus can be considered constant.

Note: Several different implementations exist for lists. Other list implementations can insert and remove from the head of the list in \(O(1)\) time. However, they typically have a slightly higher cost due to the need to allocate and deallocate memory. Later notebooks show these alternate implementations and how to make choices based on different use cases.

For dictionaries, here are some of the associated costs:

Operation	Runtime Cost
Insert a key-value pair	\(O(1)\)
Removing an entry by key	\(O(1)\)
Removing an entry by value	\(O(n)\)
Check if a value exists	\(O(n)\)
Check if a key exists	\(O(1)\)
Retrieving a value by key	\(O(1)\)

Behind the scenes, dictionaries are typically implemented through hash tables. A hash function computes an integral value from the key. We can quickly find the index where the key is (or should be placed) within the table from that value. This processs allows for the \(O(1)\) runtime cost, albeit the constant cost is higher due to the need to compute the hash value. Collisions can also exist when the hash values map to the same index in the table; this requires implementations to check for equality when retrieving a value by key. Future notebooks will provide more details.

19.3. References revisited#

Unlike other programming languages in which a variable can directly hold a value (e.g., in C++, int i = 4;, i has the value of 4), variables in Python contain references to objects stored somewhere in memory. An object in Python can be just about anything - a number, a string, a list, a function, an instance of custom class, etc. When we assign a value to a variable, we actually store a reference in that variable to the object that holds the corresponding value.

Developers must understand references to effectively manage memory and prevent unexpected side effects.

Creating objects: When we create an object (either by using a literal such as 5, “hello”, etc. or by using a constructor), Python allocates memory to store that objects’s data as well as additional metadata to track the object’s ID and the number of active references to that object.
Variable assignment: When we assign a variable to an object, we are actually assigning a reference to that object that holds the value. In the following code, Python first creates four objects to represent the four string literals. The interpreter then allocates a list object and then assigns references to the 4 string objects within the list. In the next statement, the interpreter assigns the same reference that x contains to y.
```
x = ["Duke", "UNC", "NCSU", "Notre Dame"]
y = x
print(y[3])
```
Reference Counts: Python tracks how many active references point/refer to an object. When that count drops to zero, the memory allocated to the object can be automatically freed (garbage collected) at some point. No guarantee exists as to when the memory will actually be freed. After the first statement above, each of the five objects has a reference count of one. After the second statement, the list now has an active reference count of two. Then, when the scope for that code block exists, the reference count for the list goes to zero. Once the list has been actually freed, the reference counts for the four string objects drop to zero and those can be automatically freed at some point.
Aliases: When we create multiple variables that refer to the same object, those variables are considered aliases of each other. Above, x and y are aliases for the same list object.
Immutable: Python has number of object types that are immutable (e.g., numbers, strings, tuples, etc.) Once the object has been created and initialized, the underlying values (state) cannot be changed. When we perform operations that appear to modify an immutable object, we are actually creating a new object and updating the corresponding reference.
```
x = 1   # x references an integer object with a value of 1
y = x   # y now referenecs that same object, which now has a reference count of 2
x = 2   # x now refers to a new integer object that has a value of 2. 
```
Mutable: When changing the state (values) in a mutable object such as a list or dictionary, those changes are reflected across all of the variables that contain the same reference. Ultimately, they just refer to the same underlying object.

x = ["Duke", "UNC", "NCSU", "Notre Dame"]
y = x
x.append("Wake Forest")   # since x and y are aliases pointing to the same object, this change only occurs once
                          # even it appears to occur in both x and y.
print("ID:",id(x),x)
print("ID:",id(y),y)

ID: 4398392448 ['Duke', 'UNC', 'NCSU', 'Notre Dame', 'Wake Forest']
ID: 4398392448 ['Duke', 'UNC', 'NCSU', 'Notre Dame', 'Wake Forest']

19.4. Suggested LLM Prompts#

Explain the RAM model of computation and its importance in analyzing the time complexity of algorithms. Provide an example to illustrate the concept.
Explain big O notation and how it is used to analyze time and space complexity for computer algorithms.
What is the role of Big O in designing efficient software?
Discuss the trade-offs between time and space complexity in algorithm design. Provide examples of algorithms that prioritize time efficiency over space efficiency and vice versa, and explain when each approach might be appropriate.
Implement a recursive function and analyze its time complexity. Discuss the trade-offs between iterative and recursive approaches in terms of time and space complexity.
Explain the concept of amortized time complexity and provide an example where it is useful. How does it relate to the time complexity of dynamic array operations in Python?
You need to store and access a collection of unique elements efficiently. Explain when you would choose a set over a list or a dictionary, and how the time complexity of common operations (insertion, deletion, membership testing) differs between these data structures. Provide an example use case for sets.
You need to store key-value pairs where the keys are unique, and you want to be able to quickly retrieve the value associated with a given key. Discuss the advantages and disadvantages of using a dictionary over other data structures like lists or sets. Explain how dictionaries are implemented internally and the time complexity of common operations like insertion, deletion, and lookup.
You need to store and access a sequence of elements by their position in the sequence. Compare and contrast the use of lists, tuples, and arrays (from the array module) for this purpose. Discuss the time complexity of common operations like indexing, slicing, and concatenation for each data structure, and provide examples of when you might choose one over the others.
You need to store and access elements based on their priority or sort order. Explain when you would choose a heap (implemented using the heapq module) over other data structures like lists or dictionaries. Discuss the time complexity of common operations on heaps, such as pushing, popping, and peeking at the smallest or largest element.
You need to store and manipulate a collection of elements in a specific order, and you frequently need to insert or remove elements from the beginning or end of the collection. Explain the advantages and disadvantages of using a deque (double-ended queue) from the collections module over a list for this purpose. Discuss the time complexity of common operations on deques and lists. Provide a financial example using a deque to manage a task such as order processing.
Explain the concept of references in Python. How are references different from variables in other programming languages? Provide an example to illustrate how variables in Python store references to objects rather than holding the values directly.
Explain the concept of reference counting in Python. How does Python keep track of the number of active references to an object, and what happens when the reference count drops to zero? Provide an example to illustrate the reference counting mechanism and its impact on memory management. What is the impact of circular references?

19.5. Review Questions#

Provide the O() runtime for the following operations:
1. checking if a value exists in a list
2. inserting an element at the start of a list
3. removing an element at the start of a list
4. removing an element at the end of a list
5. checking if a key exists in a dictionary
6. checking if a value exists in a dictionary.
Which of those operations executes the fastest?
What is the primary focus of the field called “analysis of algorithms”?
Explain the RAM (Random Access Machine) model of computation and its key assumptions.
How does the RAM model treat the time cost of loops and functions?
Explain the concept of asymptotic analysis and its purpose in analyzing algorithms.
Why is it useful to discard constants and focus on the growth rate in Big O notation?
Why is it important to choose the right data structure for a given problem?
What is the purpose of reference counting in Python’s memory management?
Explain the concept of aliases in Python and how they can lead to unexpected side effects.

answers

19.6. Exercises#

Performance Comparison: Sorting Algorithms Using the bubble sort code above, compare the performance of sorting various arrays to using merge sort (code below). You’ll need to remove the intermediary print() calls from bubblesort.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
 
    # Divide the array into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
 
    # Recursively sort each half
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
 
    # Merge the sorted halves
    return merge(left_half, right_half)

def merge(left, right):
    merged = []
    left_idx, right_idx = 0, 0
 
    # Compare elements from both lists and append the smaller one to the merged list
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            merged.append(left[left_idx])
            left_idx += 1
        else:
            merged.append(right[right_idx])
            right_idx += 1
 
    # Append the remaining elements from the left and right lists
    merged.extend(left[left_idx:])
    merged.extend(right[right_idx:])
 
    return merged

# Example usage:
arr = [3, 6, 8, 10, 1, 2, 5, 7, 9, 4]
sorted_arr = merge_sort(arr)
print("Sorted array:", sorted_arr)  

Use the %%timeit command in Jupyter notebooks to run this experiment. You should try passing a sorted array, a reverse sorted array, a mixed up array, and a longer array (greater than 100 elements) to see some of the performance differences.

Asymptotic Analysis: Determine the Big O running time of the following functions:

def sum_list(lst):
    total = 0
    for x in lst:
        total += x
    return total

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1

def binary_search(lst, target):
    low = 0
    high = len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

19.7. References#

[1] Steve Skiena. 2020. The Algorithm Design Manual, 3rd Ed., Springer. https://doi.org/10.1007/978-3-030-54256-6