Big-O Analysis
A)
You have a name, and you want to find the person’s phone number in the phone book. How many steps will it take in Big-O notation? (There are
n
entries in the phone book, which is in alphabetical order – you can easily open the phone book to its middle if you want to.)
B)
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!) How many steps will it take in Big-O notation? (There are
n
entries in the phone book, which is in alphabetical order.)
C)
You want to read the numbers of every person in the phone book. How many steps will it take in Big-O notation? (There are
n
entries in the phone book, which is in alphabetical order)
D)
You want to read the numbers of just the As. How many steps will it take in Big-O notation? (There are
nentries in the phone book, which is in alphabetical order)
E)
Suppose you are building an app to keep track of your finances. Every day, you write down everything for which you spent money. Once you record an entry, you do not look at that entry until the end of the month. You keep the entries grouped by category – all the food together, health expenses together, etc. At the end of the month, you review your expenses and sum up how much you spent (on all items) in each category. So, you have lots of inserts and a few reads. Should you use an array or a list?
F)
What is the Big-O running time of “Doubling the value of each even element in an array.”? (The array hasnvalues.) You need only write down the final Big-O runtime – no need to put down the intermediate equations.
G)
What is the Big-O running time of “Doubling the value of just the first element in an array.”? (The array has
nvalues.) You need only write down the final Big-O runtime – no need to put down the intermediate equations.
H)
What is the Big-O running time of “Creating a multiplication table with all the elements in the array.”? If your array has
n
values in it, you are going to create a
n
x
n
matrix to hold the multiplication table. You need only write down the final Big-O runtime – no need to put down the intermediate equations.