Big O

Question 1

Insert in ordered array

Answer 1

O(n)

Question 2

Removal from ordered array

Answer 2

O(n)

Question 3

Linear Search # of comparisons Best Case

Answer 3

found as first element

1 comparison

Question 4

Linear Search # of comparisons worst case

Answer 4

n comparisons

when element is last element or not in the array

Question 5

Linear Search number of comparisons in average case

Answer 5

(3n+1)/4 comparisons

Question 6

Binary Search # of comparisons best case

Answer 6

1 comparison

element wanted is in the middle of the array

Question 7

Binary search # of comparisons worst case

Answer 7

log(n) + 1 comparisons

Question 8

Binary Search # of comparisons average case

Answer 8

closer to worst case then best case

more likely to find the element as the search space gets smaller

Question 9

Selection Sort Barometer Operation

Answer 9

n*(n-1)/2

Question 10

Selection Sort # of swaps

Answer 10

n-1

Question 11

Insertion sort # of comparisons Worst case

Answer 11

n*(n-1)/2

Question 12

Insertion sort # of comparisons best case

Answer 12

n comparisons (no moves)

Question 13

Insertion sort # of comparisons average case

Answer 13

n*(n-1)/4

Question 14

Quick sort best case run time

Answer 14

O(n log n)

Question 15

Quick sort average case run time

Answer 15

O( n log n)

Question 16

Quick sort worst case run time

Answer 16

O(n^2)

Question 17

Selection sort best case run time

Answer 17

O(n^2)

Question 18

Selection sort average case run time

Answer 18

O(n^2)

Question 19

Selection sort worst case run time

Answer 19

O(n^2)

Question 20

Insertion sort best case run time

Answer 20

O(n)

Question 21

Insertion sort average case run time

Answer 21

O(n^2)

Question 22

Insertion sort worst case run time

Answer 22

O(n^2)

Question 23

Mergesort best case run time

Answer 23

O(n log n)

Question 24

Merge sort average case run time

Answer 24

O(nlogn)

Question 25

Merge sort worst case run time

Answer 25

O(nlogn)

Question 26

HeapSort best case run time

Answer 26

O(nlogn)

Question 27

HeapSort average case run time

Answer 27

O(nlogn)

Question 28

HeapSort worst case run time

Answer 28

O(nlogn)

Question 29

Data structure- insertion, delete, look up - run time

Answer 29

O(log n)

Question 30

BST insertion, removal, search cost

Answer 30

O(height)

Question 31

sorting an array with BST run time

Answer 31

O(n * h)

if balanced than O(nlogn)

Question 32

Run time of Priority Queues insert and remove

Answer 32

O(log n)

Question 33

Heap # of swaps for insertion

Answer 33

height swaps

Question 34

Heap number of comparisons for removal

Answer 34

height * 2 compariosns

Question 35

Run time for insertions and removal from a heap

Answer 35

O(log n)

Question 36

Heap removal of a node run time

Answer 36

O(logn)

Question 37

Heap removal of a node run time

Answer 37

O(nlogn)

Question 38

cost to heapify an array

Answer 38

O(n)

Question 39

Time complexity of Radix Sort

Answer 39

O(n*k)

where n values of at most k digits