sorting + searching

Question 1

bubble sort: what is the best runtime?

Answer 1

O(n)

Question 2

bubble sort: what is the worst runtime?

Answer 2

O(n^2)

Question 3

bubble sort: what is the average runtime?

Answer 3

O(n^2)

Question 4

what sort method has the same runtime for all cases (average, best, worst) and what is the runtime?

Answer 4

O(n^2) for selection sort

Question 5

insertion sort: what is the best runtime?

Answer 5

O(n)

Question 6

insertion sort: what is the average runtime?

Answer 6

O(n^2)

Question 7

insertion sort: what is the worst runtime?

Answer 7

O(n^2)

Question 8

disadvantages of the selection sort?

Answer 8

it will not exit the sort if it sorts the array at an earlier point than O(n^2)

Question 9

structure of a bubble sort?

Answer 9

for loop

Question 10

structure of a selection sort?

Answer 10

for loop within a for loop

Question 11

structure of an insertion sort?

Answer 11

for loop with nested while loop

Question 12

quick sort: best runtime

Answer 12

O(n log (n))

Question 13

quick sort: average runtime

Answer 13

O(nlog(n))

Question 14

quick sort: worst runtime

Answer 14

O(n^2)

Question 15

structure of quicksort

Answer 15

a while loop with two nested while loops and one nested if statement

Question 16

what array type is used for quick sort?

Answer 16

primitive types

Question 17

what is the runtime for all cases of Merge sort?

Answer 17

O(nlog(n))

Question 18

structure of merge sort

Answer 18

three unnested while loops, the first while loop has an if/else nested

Question 19

best runtime for binary search

Answer 19

O(1)

Question 20

worst and average runtime for binary search

Answer 20

O(log(n))

Question 21

best runtime for linear/sequential search

Answer 21

O(1)

Question 22

worst and average runtime for linear and sequential search

Answer 22

O(n)

Question 23

prerequisite for binary search

Answer 23

the array must be in order

Question 24

what does binary search do?

Answer 24

outputs the index of the item your are searching for in the array. If it is not in the array, it outputs -1.