Big O Notation

Question 1

What is Big O Notation?

Answer 1

the language we use to talk about how efficient an algorithm is

Question 2

What is constant time?

Answer 2

The time doesn’t change relative to input size

Question 3

What is the notation for constant time?

Answer 3

O(1)

Question 4

O(1) is what BigO notation?

Answer 4

Constant Time

Question 5

What is linear time?

Answer 5

The time will change at the same rate as the input

Question 6

Give a code example of linear time

Answer 6

A func that prints every item of an array:

func printAllItems(in items: [Int]) {
for item in items {
print(item)
}
}

Question 7

Give a code example of constant time

Answer 7

Accessing one element in an array by index:

func printFirstItem(in items: [Int]) {
print(items[0])
}

Question 8

What is the notation for linear time?

Answer 8

O(n)

Question 9

O(n) is what BigO notation?

Answer 9

Linear time

Question 10

What is quadratic time?

Answer 10

The time required to execute a command is square of the input

Question 11

What is the notation for quadratic notation?

Answer 11

O(n^2)

Question 12

O(n^2) is what BigO notation?

Answer 12

Quadratic notation

Question 13

Give a code example of quadratic notation?

Answer 13

Iterating over nested loops:

func printAllPossibleOrderedPairs(in items: [Int]) {
for firstItem in items {
for secondItem in items {
print(firstItem, secondItem)
}
}
}

Question 14

Is BigO usually concerned with Worst, Average, or Best case scenarios?

Answer 14

Worst

Question 15

What are the two complexities that BigO can refer to?

Answer 15

Time and Space

Question 16

Identify the time complexity:

func printAllPossibleOrderedPairs(in items: [Int]) {
for firstItem in items {
for secondItem in items {
print(firstItem, secondItem)
}
}
}

Answer 16

Quadratic, O(n^2), because theres nested loops

Question 17

Identify the time complexity:

Accessing one element in an array by index:

func printFirstItem(in items: [Int]) {
print(items[0])
}

Answer 17

O(1), constant

Question 18

Identify the time complexity:

func printAllItems(in items: [Int]) {
for item in items {
print(item)
}
}

Answer 18

Linear, O(n)

Question 19

Free card

Answer 19

Have some good karma

Question 20

What is the time complexity of an array lookup by index?

Answer 20

O(1)

Question 21

What is the time complexity of a hash lookup?

Answer 21

O(1) on average bc of potential collisions

Question 22

What is x?

x = log(2, 16)

Answer 22

4

Question 23

What is x?

x = log(3, 9)

Answer 23

2

Question 24

What is x?

x = log(5, 25)

Answer 24

2

Question 25

What is the notation for a logarithmic algorithm?

Answer 25

O(log n)

Question 26

O(log n) is what BigO notation?

Answer 26

Logarithmic

Question 27

Give an example of a logarithmic algorithm and explain why

Answer 27

Binary Search because each step exponentially reduces the input size

Question 28

A logarithm is the inverse function to what?

Answer 28

exponents

Question 29

What is the time complexity of binary search? why?

Answer 29

O(log n) because the search input decreases in size logarithmically

Question 30

Identify the bigO notation and explain why

for i in stride(from: 0, to: n, by: 1) {
for j in stride(from: 1, to: n, by: 1) {
for k in stride(from: 1, to: n, by: 1) {
// do constant time stuff
}
}
}

Answer 30

O(n^3), cubic, because theres 3 levels of nested loops

Question 31

Identify the notation:

it only takes a single step for the algorithm to accomplish the task.

Answer 31

Constant: O(1)

Question 32

Identify the notation:

The number of steps it takes to accomplish a task are decreased by some factor with each step.

Answer 32

Logarithmic: O(log n)

Question 33

Identify the notation:

The number of of steps required are directly related to the input

Answer 33

Linear: O(n)

Question 34

Identify the notation:

The number of steps it takes to accomplish a task is square of n

Answer 34

Quadratic: O(n^2)

Question 35

Identify the notation:

The number of steps it takes to accomplish a task is a constant to the n power (pretty large number)

Answer 35

Exponential: O(k^n)

Question 36

What is a logarithm?

Answer 36

The power that a number needs to be raised to in order to get another number

Question 37

Define: The power that a number needs to be raised to in order to get another number

Answer 37

Logarithm

Question 38

What is the time complexity for an algorithm that calculates a Fibonacci number using recursion? and why?

Answer 38

exponential, o(2^n), because each iteration calls itself twice. Because the iteration returns ( fib(n-1) + fib(n-2) ).

Question 39

Which function is the inverse of exponential?

Answer 39

Logarithmic

Question 40

Which function is the inverse of logarithmic?

Answer 40

Exponential

Question 41

Whats the difference between quadratic notation and exponential notation?

Answer 41

quadratic == n^2
exponential == x^y