Popcorn Hack #1

Here’s an array of numbers:

arr = [1, 2, 3, 4, 5]

  • Print the third item from the array using constant time (O(1)).
  • Print all the items from the array using linear time (O(n)).
arr = [1, 2, 3, 4, 5]

print(arr[2])

for num in arr:
    print(num)

3
1
2
3
4
5

Popcorn Hack #2

Given the array of numbers from 1-3 (arr = [1,2,3]). Write a function that prints all the different unique pairs of numbers from the array. For example the output of this array should be: (1,2) (1,3) (2,3)

Addtionally, what time complexity is this code? Write a small explanation.

arr = [1,2,3]

for i in arr:
    for j in arr:
        if i != j and i < j: ## keeps the numbers unique but still O(n^2)
            print(i, j)

## This code has a time complexity of O(n^2) because it has to go over each element in the array 2 times, so it makes the comparison a total of n^2 times. Or in this case (3)^2 times

1 2
1 3
2 3

Popcorn Hack #3

Which of these is inefficient for large inputs?

a) Linear Time
b) Factorial Time
c) Constant Time
d) Linearithic Time

B is inefficient because it takes the longest time.

Which of these can be represented by a nested loop?

a) Logarithmic Time
b) Linearithmic Time
c) Quadratic Time
d) Linear Time

C is represented by a nested loop because it has to make O(n^2) comparisons

Homework Hack

Write a function that takes the following inputs:

An array: arr = [5, 10, 15, 20, 25] A string representing the time complexity: “constant”, “linear”, “quadratic”, etc. The function should perform operations on the array based on the given time complexity. For example:

If the string is “constant”, return the first item of the array. If the string is “linear”, print all the items in the array. If the string is “quadratic”, print all pairs of items in the array.

def search_with_time_complexity(array, time_complexity):
    if time_complexity == "constant":
        print(array[0])
        return
    elif time_complexity == "linear":
        for item in array:
            print(item)
        return
    elif time_complexity == "quadratic":
        for i in arr:
            for j in arr:
                if i != j and i < j:
                    print(i, j)
        return
    else:
        return "bad time complexity"
    
arr = [5, 10, 15, 20, 25]

print('constant:')
search_with_time_complexity(arr, "constant")
print('linear:')
search_with_time_complexity(arr, "linear")
print('quadratic:')
search_with_time_complexity(arr, "quadratic")

constant:
5
linear:
5
10
15
20
25
quadratic:
5 10
5 15
5 20
5 25
10 15
10 20
10 25
15 20
15 25
20 25