Clicker Questions - 17-Big-O
Clicker Questions
Question 1: Suppose I have a square lawn with a width of n feet. And suppose I want to fence it in the following way: I'm going to set a 4"x4"by4' wooden post every six feet (potentially less in the corners). And I am going to run three 1"x3"x6' wooden boards between every consecutive pair of posts. Please give me the cleanest big-o expression of number boards and posts I will have to purchase.
Answer
For each side of the fence, you'll need roughly $\frac{n}{6}$ posts and $3(\frac{n}{6})$ boards. Their sum is $O(n)$ and four times this is also $O(n)$.Question 2: Suppose it takes me 2 seconds to mow a 6'x1' rectangle in my field. Please give me the cleanest big-o expression of number of minutes that it takes me to mow my lawn.
Answer
$O(n^{2})$: The area is $n^{2}$ square feet, and you can partition that into 6 square-foot regions to mow. That's roughly $n^{2} / 6$, which is $O(n^{2})$. On your clicker answer, you can write "n^2" or "n*n".Question 3: Suppose my field is an equilateral triangle whose sides are each $n$ feet long. Please give me the cleanest big-o expression of the number of pieces of wood that I have to purchase in order to fence it like I did in question 1.
Answer
Now there are three sides instead of four. It's still $O(n)$.Question 4: It's n miles to to the mountains, and there are 5 stop lights. I have to wait up to 50 seconds at a light. If I'm really unlucky and reach each stop light just as it’s turning red, but otherwise I drive at an average of 50 MPH, please give me the cleanest big-o expression for the number of hours it takes me to get to the mountains.
Answer
Your time is $\frac{n}{50}$ hours plus $5 \times 50$ seconds. This is an equation of the form $a \times n + b$, where $a$ and $b$ are constants, which is $O(n)$.Question 5: Suppose I have a computer memory with $n$ bits, and I’m going to store just one number on it. Please give me the cleanest big-o expression for how many different numbers can I store in the memory?