Note: those marked with an asterisk I am not 100% confident in my answer/reasoning.
Please feel free to discuss the problems and my proposed solutions below!
2.1
Here is my proof for this problem:
and here are my reasonings for each numbered step:
- Constant multiple property of logs.
f = O(g)was given.- Function composition of Big-O
log(n) = O(log(n)by identity property of Big-O.f = O(g)was given.
- Multiplicative property of Big-O.
- Constant multiple property of Big-O.
Thus, A should be the right answer.
2.2
Because of the composition property of Big-O, the proposed statement is true. Answer choice A is definitely correct, and I believe D is just another way of stating what f = O(g) means mathematically. So both A and D are correct.
Turns out that my previous answer was incorrect. I was presented a counter example, f = 2n and g = n. Thus, A is not correct, and it should be C and D.
2.3
A, C, E, D, B
2.4
E, A, B, D, C
2.5
A, E, C, B, D