a) 1 [40%] Prove or disprove each of the followings. 5n0.5 + n = (100n). 0.In = 2n29). n = O(n2.0). Oologn) + (n)= en). O(logn) = 0(1). O(1) + O(1) + ... + O(1) [1,000,000 terms] =0(0.001). maxfin), g(n)} = o(fin) + g(n)), where f(n) and g(n) are positive functions. min{fin), g(n)} = 92 (fin) + g(n)), where f(n) and g(n) are positive functions. (1) + S2(1) = 2(1). fin) = (fin) + c), where c is a positive constant and f(n) is a positive function. On) + (n)=2(loglog n). n+2 )=2n). m) If f(n) = O(n), then 2) = (2"), where f(n) is a positive function. 0.51 = o(122). 4log,000n = o(log.n). If ) = (g(n)), then log (f(n)) = o(log g(n)), where f(n) and g(n) are positive functions. ((n) + ((n)=2(n). Ang(n) - (n)), where f(n) and g(n) are positive functions. If f(n) = (g(n)), then f(n) = 2(20 g(n)), where f(n) and g(n) are positive functions. If there are only finite number of points for which f(n) > g(n), then f(n)= O(g(n)), where f(n) and g(n) are positive functions