searching

Question 1

linear search

Answer 1

checks each item of the list systematically to see if it matches the key - O(n)

Question 2

expected values

Answer 2

the sum of each potential outcome multiplied by its probability:
x1P(X=x1) + x2(P(X=x2) + … + xn*P(X=xn)

Question 3

sorted linear search

Answer 3

if list sorted in ascending order search can be stopped once an element is reached that is larger than the key

Question 4

binary search

Answer 4

divide and conquer - calculates mid point of sorted list, if mid point greater than search term discard mid point + if smaller discard mid point -, repeat until key is mid point or no items remain - O(log(n))

Question 5

SCAN

Answer 5

o(n^2) - for each element all other elements are checked to see if they are equal

Question 6

STOR

Answer 6

o(n) - loops through once, in a second array the value of the element is used as the key to a second array, that index incremented, if any index > 1 duplicates occur - second array, must have length greater than largest value of first array, and first array must only contain ints

Question 7

interpolation search

Answer 7

like binary search but uses weighted guess for midpoint - midpoint calculated by [(key - a[i])/(a[j]-a[i]) * j - i]