CSI

Best to Worst Time Complexities

O(1), O(log n), O(n), O(n log n), O(n²), O(2^n), O(n!)

Linear Search Time Complexities: Best to Worst

O(1), O(n), O(n)

Binary Search Time Complexities: Best to Worst

O(1), O(log n), O(log n)

Insertion Sort Time Complexities: Best to Worst

O(n), O(n²), O(n²)

Merge Sort Time Complexities: Best to Worst

O(n log n), O(n log n), O(n log n)

Quicksort Time Complexities: Best to Worst

O(n), O(n log n), O(n²)

3 types of errors

Syntax, runtime, semantic (bad mental)

Dataclasses

from dataclasses import dataclass

Concatenations (+)

Only works with like types. Concatenation does not change the original variable

Lists (functions)

pop() and insert(). These are destructive, they permanently modify the list

Extending (+=)

Modifies the original variable

Tokens

Each element of a split string. A list of substrings. The original string is not modified. Delimiter is what string is in the split parentheses

Values Types

int, float, bool

Passing by Value

When a value type is passed in as an argument to a function, a copy is made. Changes made to the copy in the function have no permanent effect

Reference Types

lists, dictionaries, sets

Passing by Reference

When a reference type is put in the argument of a function, the original value is referenced and can be changed from the function. The changes are permanent, and not a copy

Create a new list: Big-O

O(n)

append(): Big-O

O(1)

pop(x) or insert(x)

O(n)

pop(-1) or insert(-1)

O(1)

Concatenate (+)

O(n)

Extend n elements

O(n)

Linear Search

Begins at 0 and increases by 1. Compares each value at the index to the target. It returns the found index or None.

Binary Search

Begins looking at the midpoint. If the length is even, it looks at the left element. If the element at the midpoint is greater than the target, the target must be on the left side of the midpoint. If the element is less than the target, it must be on the right of the midpoint. It’s a divide-and-conquer algorithm

Linear Search Code

def linearsearch(arr, target):

for i in range(len(arr)):

if arr[i]==target:

return i

return None

Binary Search Code

def binarysearch(arr, target)

left = 0

right = len(arr)-1

while left<=right:

mid = (left+right)//2

if arr[mid] == target:

return mid

if arr[mid] < targetL

left = mid+1

else:

right = mid-1

return None

Insertion Sort

Divide the array into sorted and unsorted. The left element of unsorted moves to the right of sorted, then starts swapping with neighbors of sorted.

Insertion Sort Code 1

def insertionsort(list):

llist = len(list)

for i in range(1, llist):

insert_index = i

current_value = list[i]

for j in range(i-1, -1, -1):

if list[j] > currentvalue:

list[j+1] = list[j]:

insert_index = j

else:

break

list[insert_index] = current_value

Insertion Sort Code 2

def insert(list, mark):

index = mark

while index > -1 and list[index] >list[index+1]:

swap(list, index, index+1)

index = index-1

def insertionsort(list):

for mark in range(len(list)-1):

insert(list, mark)

Merge Sort

recursively splits the list in half until the length is one, then merges it back together in sorted order. It’s a divide-and-conquer method. It merges small lists together by comparing the first elements in each

Merge Sort Code

def merge(left, right):

sorted_list = []

i = 0

j = 0

while i <len(left) and j <len(right):

if left[i] <right[j]:

sorted_list.append(left[i])

i+=1

else:

sorted_list.append(right[j])

j+=1

sorted_list.extend(left[i:])

sorted_list.extend(right[j:])

return sorted_list

def merge_sort(arr):

if len(arr) <=1:

return arr

mid = len(arr)//2

left_half = merge_sort(arr[:mid])

right_half = merge_sort(arr[mid:])

return merge(left_half, right_half)

Open addressing

Will look for the next open address to put store the value

Chaining

appends the value to the address (making it a list in the values.

Quick sort

Divide-and-conquer method. Pivot value is usually at index 0. Divides the list into three partitions. elements less than pivot, elements equal to pivot, and elements greater than pivot. it sorts smaller lists and merges them back together in sorted order

.sort()

destructive in-place sort

.sorted()

creates a sorted copy

Hash Function

Given an arbitrary input value, produces a number as output. The output is called hash code. Not all types in Python are hashable. A set is a hashing data structure

Indexing function

Makes the hashed code smaller to fit into a smaller array.

Any, Union

from typing import Any, Union