1. Consider a hypothetical algorithm that executes its basic operation t(n) = 300n^2 + 150n + log(n) times for every input of size n. Prove, using the definition of notation, that t(n) (n^2 ).

2. Consider three functions:

t1(n) = log n

t2(n) = n

t3(n) = n(n1)/2

Classify each of the following statements as True or False. 4.1 t1(n) (t1(n)) 4.2 t1(n) (t1(n)) 4.3 t1(n) O(t1(n)) 4.4 t1(n) (t2(n)) 4.5 t1(n) (t2(n)) 4.6 t1(n) O(t2(n)) 4.7 t1(n) (t3(n)) 4.8 t1(n) (t3(n)) 4.9 t1(n) O(t3(n)) 4.10 t2(n) (t1(n)) 4.11 t2(n) (t1(n)) 4.12 t2(n) O(t1(n)) 4.13 t2(n) (t2(n)) 4.14 t2(n) (t2(n)) 4.15 t2(n) O(t2(n)) 4.16 t2(n) (t3(n)) 4.17 t2(n) (t3(n)) 4.18 t2(n) O(t3(n)) 4.19 t3(n) (t1(n)) 4.20 t3(n) (t1(n)) 4.21 t3(n) O(t1(n)) 4.22 t3(n) (t2(n)) 4.23 t3(n) (t2(n)) 4.24 t3(n) O(t2(n)) 4.25 t3(n) (t3(n)) 4.26 t3(n) (t3(n)) 4.27 t3(n) O(t3(n))