Big O Notations

Question 1

What are the Asymptotic Notation types?

Answer 1

Big O
Big Theta Θ
Big Omega Ω

Question 2

What is the root meaning of Asymptotic?

Answer 2

The word asymptotic stems from the Greek root meaning “not falling together”. In ancient Greek mathematics the conic sections studied where deemed hyperbolas such as a graph where y = x and y = -x. The lines of both y values of x and -x curved lines on the graphs approach each other but never touch when x ➜ ∞.

Question 3

O(1) space complexity denotes?

Answer 3

The amount of memory used is constant and is not dependent on data processing.

Question 4

Which line on the graph represents constant time?

Answer 4

Line A (green line)

Question 5

Which line represents logarithmic time complexity?

Answer 5

Line B (yellow line)

Question 6

Which line represents linear time complexity?

Answer 6

Line c (blue line)

Question 7

Which line represents quadratic time complexity?

Answer 7

Line d (red line)

Question 8

Algorithms that are said to take the same amount of time executed are called?

Answer 8

Constant time algorithms

Question 9

If the execution time of this algorithm is independent of the size of input, it is considered why type of complexity?

Answer 9

O(1) Constant Time

Question 10

What type of complexity is an algorithm if the time to execute is directly proportional to the input size?

Answer 10

O(n) Linear Time Complexity

Question 11

Binary search is an example of which time complexity?

Answer 11

O(log n) Logarithmic Time Complexity

Question 12

What time complexity is the time it takes to run an algorithm is proportional to the logarithm of the input size n?

Answer 12

O(Log n) Logarithmic Time Complexity

Question 13

What time complexity is an algorithm if the time to execution is proportional to the square of the input size?

Answer 13

O(n^2) Quadratic Time Complexity

Question 14

Checking to see whether there are any duplicates in a deck of cards is an example of which time complexity?

Answer 14

O(n^2) Quadratic Time Complexity

Question 15

Algorithms involving nested iterations such as nested loops are which type of time complexity?

Answer 15

O(n^2) Quadratic Time Complexity

Question 16

Bubble sort is an example of which time complexity?

Answer 16

O(n^2) Quadratic Time Complexity

Question 17

Selection sort is an example of which time complexity?

Answer 17

O(n^2) Quadratic Time Complexity

Question 18

Insertion sort is an example of which time complexity?

Answer 18

O(n^2) Quadratic Time Complexity

Question 19

Accessing arrays on average has which time and space complexity?

Answer 19

Time = Θ(1)
Space worst case = O(n)

Question 20

Searching arrays, on average, has which time and space complexity?

Answer 20

Time average: Θ(n)
Space worst: O(n)

Question 21

Array insertion, on average, has which time and space complexity?

Answer 21

Time average: Θ(n)
Space worst: O(n)

Question 22

Array deletion, on average, has which time and space complexity?

Answer 22

Time average: Θ(n)
Space worst: O(n)

Question 23

What is the best time complexity and the worst space complexity for array quicksort algorithms?

Answer 23

Time best: Ω(n log(n))
Space worst: O(log(n))

Question 24

What is the best time complexity and the worst space complexity for array mergesort algorithms?

Answer 24

Time best: Ω(n log(n))
Space worst: O(n)

Question 25

What is the best time complexity and the worst space complexity for array Timsort algorithms?

Answer 25

Time best: Ω(n) Space worst: O(n)

Question 26

What is the best time complexity and the worst space complexity for array heapsort algorithms?

Answer 26

Time best: Ω(n log(n)) Space worst: O(1)

Question 27

What is the best time complexity and the worst space complexity for array bubble sort algorithms?

Answer 27

Time best: Ω(n) Space worst: O(1)

Question 28

What is the best time complexity and the worst space complexity for array insertion sort algorithms?

Answer 28

Time best: Ω(n) Space worst: O(1)

Question 29

What is the best time complexity and the worst space complexity for array selection sort algorithms?

Answer 29

Time best: Ω(n^2) Space worst: O(1)

Question 30

What is the best time complexity and the worst space complexity for array tree sort algorithms?

Answer 30

Time best: Ω(n log(n)) Space worst: O(n)

Question 31

What is the best time complexity and the worst space complexity for array shell sort algorithms?

Answer 31

Time best: Ω(n log(n)) Space worst: O(1)

Question 32

What is the best time complexity and the worst space complexity for array bucket sort algorithms?

Answer 32

Time best: Ω(n + k) Space worst: O(n)

Question 33

What is the best time complexity and the worst space complexity for array radix sort algorithms?

Answer 33

Time best: Ω(nk) Space worst: O(n + k)

Question 34

What is the best time complexity and the worst space complexity for array counting sort algorithms?

Answer 34

Time best: Ω(n + k) Space worst: O(k)

Question 35

What is the best time complexity and the worst space complexity for array cube sort algorithms?

Answer 35

Time best: Ω(n) Space worst: O(n)

Question 36

What is the average time complexity and the worst space complexity for stack access algorithms?

Answer 36

Time average: Θ(n) Space worst: O(n)

Question 37

What is the average time complexity and the worst space complexity for Queue access algorithms?

Answer 37

Time average: Θ(n) Space worst: O(n)

Question 38

What is the average time complexity and the worst space complexity for stack search algorithms?

Answer 38

Time average: Θ(n) Space worst: O(n)

Question 39

What is the average time complexity and the worst space complexity for stack insertion algorithms?

Answer 39

Time average: Θ(1) Space worst: O(n)

Question 40

What is the average time complexity and the worst space complexity for stack deletion algorithms?

Answer 40

Time average: Θ(1) Space worst: O(n)

Question 41

What is the average time complexity and the worst space complexity for Queue insertion algorithms?

Answer 41

Time average: Θ(1) Space worst: O(n)

Question 42

What is the average time complexity and the worst space complexity for Queue deletion algorithms?

Answer 42

Time average: Θ(1) Space worst: O(n)

Question 43

What is the average time complexity and the worst space complexity for Singly-Linked Lists access algorithms?

Answer 43

Time average: Θ(n) Space worst: O(n)

Question 44

What is the average time complexity and the worst space complexity for Doubly-Linked Lists access algorithms?

Answer 44

Time average: Θ(n) Space worst: O(n)

Question 45

What is the average time complexity and the worst space complexity for Singly-Linked Lists search algorithms?

Answer 45

Time average: Θ(n) Space worst: O(n)

Question 46

What is the average time complexity and the worst space complexity for Doubly-Linked Lists search algorithms?

Answer 46

Time average: Θ(n) Space worst: O(n)

Question 47

What is the average time complexity and the worst space complexity for Singly-Linked Lists insertion algorithms?

Answer 47

Time average: Θ(1) Space worst: O(n)

Question 48

What is the average time complexity and the worst space complexity for Doubly-Linked Lists insertion algorithms?

Answer 48

Time average: Θ(1) Space worst: O(n)

Question 49

What is the average time complexity and the worst space complexity for Singly-Linked Lists deletion algorithms?

Answer 49

Time average: Θ(1) Space worst: O(n)

Question 50

What is the average time complexity and the worst space complexity for Doubly-Linked Lists deletion algorithms?

Answer 50

Time average: Θ(1) Space worst: O(n)

Question 51

What is the average time complexity and the worst space complexity for Skip List access algorithms?

Answer 51

Time average: Θ(log(n)) Space worst: O(n log(n))

Question 52

What is the average time complexity and the worst space complexity for Skip List search algorithms?

Answer 52

Time average: Θ(log(n)) Space worst: O(n log(n))

Question 53

What is the average time complexity and the worst space complexity for Skip List insertion algorithms?

Answer 53

Time average: Θ(log(n)) Space worst: O(n log(n))

Question 54

What is the average time complexity and the worst space complexity for Skip List deletion algorithms?

Answer 54

Time average: Θ(log(n)) Space worst: O(n log(n))

Question 55

What is the average time complexity and the worst space complexity for Hash Table search algorithms?

Answer 55

Time average: Θ(1) Space worst: O(n)

Question 56

What is the average time complexity and the worst space complexity for Hash Table insertion algorithms?

Answer 56

Time average: Θ(1) Space worst: O(n)

Question 57

What is the average time complexity and the worst space complexity for Hash Table deletion algorithms?

Answer 57

Time average: Θ(1) Space worst: O(n)

Question 58

What is the average time complexity and the worst space complexity for Binary Search Tree access algorithms?

Answer 58

Time average: Θ(log (n)) Space worst: O(n)

Question 59

What is the average time complexity and the worst space complexity for Binary Search Tree search algorithms?

Answer 59

Time average: Θ(log (n)) Space worst: O(n)

Question 60

What is the average time complexity and the worst space complexity for Binary Search Tree deletion algorithms?

Answer 60

Time average: Θ(log (n)) Space worst: O(n)

Question 61

What is the average time complexity and the worst space complexity for Binary Search Tree insertion algorithms?

Answer 61

Time average: Θ(log (n)) Space worst: O(n)

Question 62

What is the average time complexity and the worst space complexity for Cartesian Tree search algorithms?

Answer 62

Time average: Θ(log (n)) Space worst: O(n)

Question 63

What is the average time complexity and the worst space complexity for B-Tree access algorithms?

Answer 63

Time average: Θ(log (n)) Space worst: O(n)

Question 64

What is the average time complexity and the worst space complexity for B-Tree search algorithms?

Answer 64

Time average: Θ(log (n)) Space worst: O(n)

Question 65

What is the average time complexity and the worst space complexity for Cartesian Tree insertion algorithms?

Answer 65

Time average: Θ(log (n)) Space worst: O(n)

Question 66

What is the average time complexity and the worst space complexity for Cartesian Tree deletion algorithms?

Answer 66

Time average: Θ(log (n)) Space worst: O(n)

Question 67

What is the average time complexity and the worst space complexity for B-Tree insertion algorithms?

Answer 67

Time average: Θ(log (n)) Space worst: O(n)

Question 68

What is the average time complexity and the worst space complexity for B-Tree deletion algorithms?

Answer 68

Time average: Θlog (n)) Space worst: O(n)

Question 69

What is the average time complexity and the worst space complexity for Red-Black Tree search algorithms?

Answer 69

Time average: Θ(log (n)) Space worst: O(n)

Question 70

What is the average time complexity and the worst space complexity for Red-Black Tree access algorithms?

Answer 70

Time average: Θ(log (n)) Space worst: O(n)

Question 71

What is the average time complexity and the worst space complexity for Red-Black Tree insertion algorithms?

Answer 71

Time average: Θ(log (n)) Space worst: O(n)

Question 72

What is the average time complexity and the worst space complexity for Red-Black Tree deletion algorithms?

Answer 72

Time average: Θ(log (n)) Space worst: O(n)

Question 73

What is the average time complexity and the worst space complexity for Splay Tree search algorithms?

Answer 73

Time average: Θ(log (n)) Space worst: O(n)

Question 74

What is the average time complexity and the worst space complexity for Splay Tree insertion algorithms?

Answer 74

Time average: Θ(log (n)) Space worst: O(n)

Question 75

What is the average time complexity and the worst space complexity for Splay Tree deletion algorithms?

Answer 75

Time average: Θ(log (n)) Space worst: O(n)

Question 76

What is the average time complexity and the worst space complexity for AVL Tree access algorithms?

Answer 76

Time average: Θ(log (n)) Space worst: O(n)

Question 77

What is the average time complexity and the worst space complexity for AVL Tree search algorithms?

Answer 77

Time average: Θ(log (n)) Space worst: O(n)

Question 78

What is the average time complexity and the worst space complexity for AVL Tree insertion algorithms?

Answer 78

Time average: Θ(log (n)) Space worst: O(n)

Question 79

What is the average time complexity and the worst space complexity for AVL Tree deletion algorithms?

Answer 79

Time average: Θ(log (n)) Space worst: O(n)

Question 80

What is the average time complexity and the worst space complexity for KD Tree access algorithms?

Answer 80

Time average: Θ(log (n)) Space worst: O(n)

Question 81

What is the average time complexity and the worst space complexity for KD Tree search algorithms?

Answer 81

Time average: Θ(log (n)) Space worst: O(n)

Question 82

What is the average time complexity and the worst space complexity for KD Tree insertion algorithms?

Answer 82

Time average: Θ(log (n)) Space worst: O(n)

Question 83

What is the average time complexity and the worst space complexity for KD Tree deletion algorithms?

Answer 83

Time average: Θ(log (n)) Space worst: O(n)

Question 84

What is the Big O time complexity when you have a loop within a loop? a.) O(1) b.) O(n^2) c.) O(log n) d.) O(n)

Answer 84

b.) O(n^2)

Question 85

How would the following be written: O(100n^2) a.) O(100n) b.) O(n^100) c.) O(n^2) d.) O(2n^100)

Answer 85

c.) O(n^2) We drop the constant.

Question 86

What Big O is associated with Divide and Conquer? a.) O(1) b.) O(log n) c.) O(n^2) d.) O(n)

Answer 86

b.) O(log n) O(log n) is divide and conquer.

Question 87

What is the correct way to write: O(n^2 + n) ? a.) O(n^3) b.) O(3n) c.) O(n^2) d.) O(n + n^2)

Answer 87

c.) O(n^2) We drop the non-dominants.

Question 88

The most efficient Big O is: a.) O(1) b.) O(n^2) c.) O(log n) d.) O(n)

Answer 88

a.) O(1) O(1) is known as constant time.