BigO Notation

Question 1

Best scenario for linear search

Answer 1

O(1) - constant

Question 2

Average scenario for linear search

Answer 2

O(n) - linear

Question 3

Worst scenario for linear search

Answer 3

O(n) - linear

Question 4

Best scenario for binary search

Answer 4

O(1) - constant

Question 5

Average scenario for binary search

Answer 5

O(log n) - logarithmic

Question 6

Worst scenario for binary search

Answer 6

O(log n) - logarithmic

Question 7

Best scenario (time) for bubble sort

Answer 7

O(n) - linear

Question 8

Average scenario (time) for bubble sort

Answer 8

O(n^2) - polynomial

Question 9

Worst scenario (time) for bubble sort

Answer 9

O(n^2) - polynomial

Question 10

Space complexity for bubble sort

Answer 10

O(1) - constant

Question 11

Best scenario (time) for insertion sort

Answer 11

O(n) - linear

Question 12

Average scenario (time) for insertion sort

Answer 12

O(n^2) - polynomial

Question 13

Worst scenario (time) for insertion sort

Answer 13

O(n^2) - polynomial

Question 14

Space complexity for insertion sort

Answer 14

O(1) - constant

Question 15

Best scenario (time) for merge sort

Answer 15

O(n log n) - linearithmic

Question 16

Average scenario (time) for merge sort

Answer 16

O(n log n) - linearithmic

Question 17

Worst scenario (time) for merge sort

Answer 17

O(n log n) - linearithmic

Question 18

Space complexity for merge sort

Answer 18

O(n) - linear

Question 19

Best scenario (time) for quick sort

Answer 19

O(n log n) - linearithmic

Question 20

Average scenario (time) for quick sort

Answer 20

O(n log n) - linaerithmic

Question 21

Worst scenario (time) for quick sort

Answer 21

O(n^2) - polynomial

Question 22

Space complexity for quick sort

Answer 22

O(log n) - logarithmic

Question 23

Order of bigO

Answer 23

CLoLiLinPolE (Constant, Logarithmic, Linear, Linearithmic, Polynomial, Exponential)

Question 24

Explain the bigO notation O(1)

Answer 24

Constant complexity. Executes in the same amount of time regardless of data set.

Question 25

Explain the bigO notation O(log n)

Answer 25

Logarithmic complexity. Halves the data set in each pass. Efficient with large data sets. The algorithm will take one additional step each time the data (n) doubles. Log n is the inverse of exponential E.g. Binary Search

Question 26

Explain the bigO notation O(n)

Answer 26

Linear complexity. Performance is proportional to the size of the data set and increases as the data set grows. E.g. Linear Search

Question 27

Explain the bigO notation O(n log n)

Answer 27

Linearithmic. Algorithms that divide a data set but can be solved using concurrency on independent divided lists. E.g. Merge Sort

Question 28

Explain the bigO notation O(n^2)

Answer 28

Polynomial complexity. Performance is proportional to the square of the size of the data set. Efficiency is reduced with large data sets. E.g. Bubble Sort, Insertion Sort

Question 29

Explain the bigO notation O(2^n)

Answer 29

Exponential complexity. Doubles with each addition to the data set in each pass

Question 30

explain bigO - 3 marks

Answer 30

Big O defines the runtime required to execute an algorithm by identifying how the performance of your algorithm will change as the input size grows Big O = how the algorithm scales with larger data sets Evaluates the complexity of the algorithm (1) Shows how the time / memory / resources increase as the data size increases (1) Evaluates worst case scenario for the algorithm (1)