Solve in Python:

Uh-Notation. (Task 2.1) i. Prove that f(n) = (g(n)) holds if g(n) = O(f(n)) using the definition from the front page. Prove your answers. ii. Is f(n) +g(n) = (max(f(n) + g(n))? (Assume that f and g are nonnegative functions.) iii. Is (n + 100)5 = O(nb)? iv. Is 300 log(nk) + kk + 2Vk log k = O(n logn + 2k log k)? b) Analyzing Algorithms. (Task 2.2) i. Write an algorithm for the function Swap(a,i,l) that exchanges the values at position i and l in the array a, that is, after calling Swap(a,i,l), a[i] contains the former value at a[e], and a[l] contains the former value at a[i]. ii. Modify Strange Algo(n, k) to run in time (nk). (c) Designing Algorithms.Task 2.3) Design an algorithm that outputs the binary representation of a nonnegative integer x, which is a binary array a[O..n] (i.e. containing only 0 and 1) where n= log xsuch that = a[0] . 2 + a[1] . 2 + ... + a[n]. 2". Thus, a[i] is the i-th bit of x. You are only allowed to use the following arithmetic opera- tions: +,-,*,/ where / is the integer division defined as a/b = Loj. - Page 3