Chapter 1 : Binary Search, Big O

Question 1

What is Big O Notation?

Answer 1

big O notation tells you how fast an algorithm is.

Question 2

Are binary search algorithms input sorted?

Answer 2

binary search inputs are sorted

Question 3

what’s a stupid /simple search?

Answer 3

stupid search is when you start from the beginning to the end

Question 4

what is the process of binary search?

Answer 4

with binary search, you guess the middle number and eliminate half the remaining numbers every time.

Question 5

what is that the O(n) of binary search?

Answer 5

O(log n)

Question 6

why is big O called big O?

Answer 6

it’s called Big O because you put a big O infront of the number of operations

Question 7

what’s another name for O(log n)?

Answer 7

O(log n) is also known as log time. ex. Binary search

Question 8

what is an example of algorithm with a Big O of O(n* log n)

Answer 8

O(n* log n) ex.quick short

Question 9

Suppose you have a sorted list of 128 names and you’re searching through it using binary search. What’s the maximum number of steps it would take?

Answer 9

7 steps

Question 10

Suppose you have a sorted list of 256 names, and you’re searching

through it using binary search. What’s the maximum number of

steps it would take?

Answer 10

8 steps

Question 11

You have a name, and you want to find the person’s phone number in the phone book. What’s the big O

Answer 11

O(log n).

Question 12

You have a phone number, and you want to find the person’s name in the phone book. (Hint: You’ll have to search through the whole book!) What’s the big O

Answer 12

O(n)

Question 13

You want to read the numbers of just the As in a phone book? What’s the big O

Answer 13

O(n).

You may think, “I’m only doing this for 1 out of 26 characters, so the run time should be O(n/26).” A simple rule to remember is, ignore numbers that are added, subtracted, multiplied, or divided. None of these are correct Big O run times: O(n + 26), O(n - 26), O(n * 26), O(n / 26). They’re all the same as

O(n)! Why? If you’re curious, flip to “Big O notation revisited,” in chapter 4, and read up on constants in Big O notation (a constant is just a number; 26 was the constant in this question).