Clicker Questions - 16-Big-O
Clicker Questions
For each of these, please use the following multiple choice answers:
- A: $O(1)$
- B: $O(log\ n)$
- C: $O(n)$
- D: $O(n\ log\ n)$
- E: $O(n^{2})$
Question 1: Inserting an element into a multiset with $n$ elements.
Answer
$O(log\ n)$: Basic operation on a set/map/multiset/multimap.Question 2: Inserting $n$ elements into an empty multiset.
Answer
$O(n\ log\ n)$: Just memorize this for now. Actually, you can prove it by using the answer to Question 3 to show that inserting the second half of elements if $O(n\ log\ n)$.Question 3: Inserting $n$ elements into a multiset with $n$ elements.
Answer
Still $O(n\ log\ n)$. This is easier -- you are doing $n$ operations, and each of them is between $O(log\ n)$ and $O(log\ 2n)$. Since $log\ 2n$ is equal to $(log\ n)+1$, we have that the $n$ operations are bounded by $O(n\ log\ n + n)$, which is $O(n\ log\ n)$.Question 4: Erasing the first element of a vector with $n$ elements.
Answer
$O(log\ n)$: Basic operation on a set/map/multiset/multimap.Question 5: for (i = 0; i < n; i++) for (j = 0; j < i; j++) k++;.
Answer
$1 + 2 + 3 + 4 + ... + n = O(n^{2})$.Question 6: Calling push_back() on a vector with $n$ elements.
Answer
$O(1)$: Basic operation on a vector.Question 7: Creating Pascal’s triangle with $n$ levels.
Answer
Each level $i$ has $i$ entries -- this is the same as Question 5: $O(n^{2})$No Class Stats, PDF Download