Notes

Constant O(1)

numbers = list(range(1000))
print(numbers)

Time:

print(numbers[263])

ncaa_bb_ranks = {1:"Alabama",2:"Houston", 3:"Purdue", 4:"Kansas"}
#look up a value in a dictionary given a key
print(ncaa_bb_ranks[1])

Space:

def sum(a, b): 
  return a + b

print(sum(90,88))
print(sum(.9,.88))

Linear O(n)

Time:

for i in numbers:
    print(i)

Space:

def reverse_list(arr):
    n = len(arr) 
    reversed_arr = [None] * n #create a list of None based on the length or arr
    for i in range(n):
        reversed_arr[n-i-1] = arr[i] #stores the value at the index of arr to the value at the index of reversed_arr starting at the beginning for arr and end for reversed_arr 
    return reversed_arr

print(numbers)
print(reverse_list(numbers))

Quadratic O(n^2)

Time:

for i in numbers:
    for j in numbers:
        print(i,j)

Space:

def multiply_matrices(matrix1, matrix2):
    m = len(matrix1) 
    n = len(matrix2[0])
    result = [[0] * n] * m #this creates the new matrix based on the size of matrix 1 and 2
    for i in range(m):
        for j in range(n):
            for k in range(len(matrix2)):
                result[i][j] += matrix1[i][k] * matrix2[k][j]
    return result

print(multiply_matrices([[1,2],[3,4]], [[3,4],[1,2]]))

Logarithmic O(logn)

Time:

def binary_search(arr, low, high, target):
    while low <= high:
        mid = (low + high) // 2 #integer division
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

target = 263
result = binary_search(numbers, 0, len(numbers) - 1, target)

print(result)

Exponential O(2^n)

Time:

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

#print(fibonacci(5))
#print(fibonacci(10))
#print(fibonacci(20))
#print(fibonacci(30))
print(fibonacci(40))

Space:

def generate_subsets(s):
    if not s:
        return [[]]
    subsets = generate_subsets(s[1:])
    return [[s[0]] + subset for subset in subsets] + subsets

print(generate_subsets([1,2,3,4,5,6]))
#print(generate_subsets(numbers))

Hacks

  • Record your findings when testing the time elapsed of the different algorithms.

    • Images: when running the image that is only basewidth 5000, it takes 0.8 seconds to generate the image. But as I increase the basewidth, it takes longer for my computer to generate the image. For example, my computer took 7.9 seconds to generate an image with a basewidth 20000.

  • Although we will go more in depth later, time complexity is a key concept that relates to the different sorting algorithms. Do some basic research on the different types of sorting algorithms and their time complexity.

    • Time complexity I think is compressing the data so that the program runs faster. If the program is too slow, then it might not execute properly. For me, when I tried running the largest image file in the line of code, 40000, it not only took a really long time to run, but once it was done, the image didn't show up. I ran it another time and it crashed my vscode and I had to restart my computer to get it working normally again.

  • Why is time and space complexity important when choosing an algorithm?

    • I think it's important because it can effect how fast or how well the program runs. If there is not enough space then the program might stop short because there is not enough space for the algorithm to run completely. As with the previous question, if it takes a very long time, then the program might fail as well.

  • Should you always use a constant time algorithm / Should you never use an exponential time algorithm? Explain?

    • For both constant and exponential time, there are certain programs that need different types of time algorithms and not one works for all. Constant is used to access specific elements in an array whereas exponential is exponential uses a nested loop.

  • What are some general patterns that you noticed to determine each algorithm's time and space complexity?

    • The more complex the algorithms get, the more time it takes for the algorithm to run. Instead of just adding two numbers together, if you did a binary search or multiplying matrices, that would take longer.

PRACTICE PROBLEMS:

1. What is the time, and space complexity of the following code:

a = 0 b = 0 for i in range(N): a = a + random()

for i in range(M): b= b + random()

  1. O(N * M) time, O(1) space
  2. O(N + M) time, O(N + M) space
  3. O(N + M) time, O(1) space
  4. O(N * M) time, O(N + M) space

Number 3 because In the code the it looks like there are some variables being added together. I am not too sure about the space part.

2. What is the time complexity of the following code:

a = 0; for i in range(N): for j in reversed(range(i,N)): a = a + i + j;

  1. O(N)
  2. O(N*log(N))
  3. O(N * Sqrt(N))
  4. O(N*N)

I'm not quite sure about this one? I thought it was number 1 because it has the reverse function in it but it is numebr 4 and I'm not sure why.

3. What is the time complexity of the following code:

k = 0; for i in range(n//2,n): for j in range(2,n,pow(2,j)): k = k + n / 2;

  1. O(n)
  2. O(N log N)
  3. O(n^2)
  4. O(n^2Logn)

The answer is 2 because j keeps doubling.

4. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

  1. X will always be a better choice for small inputs
  2. X will always be a better choice for large inputs
  3. Y will always be a better choice for small inputs
  4. X will always be a better choice for all inputs

The answer is 2 because it makes sense that if X is more efficient than Y, then it will be better at handling the large inputs than Y, so it would be a better choice.