I is correct ii is correct

1.A) f(n) = 10 n^2 log (n^10) + n log (n^5) => o(n^2)    1.B) f(n) = 2^100 n^4 + n^3 => o (n^4)

2.A) 2 nested for inside for =>  n [n+n] = 2n^2

2.B) no. Of primitive operations (1 comparison & 1 return tot=2), 1 for println, (1 for division & 1 for recursive call) => running time is o(n)

2.C) Assignment 1, comparison 1, division 1 & assignment 1 tot=2, addition 1 & assignment 1 tot= 2 (while n), return 1 => running time o(n)

3.A) c2g(n) above f(n) and c1g(n) under f(n)

for constant c1 and no f(n) is omega (g(n)) for every n>=no || for constant c2 and no f(n) is O(g(n)) for every n>=no then f(n) = theta (g(n))

3.B) cg(n) above f(n) >> for constant c and no   f(n)= O(g(n))

3.C) cg(n) under f(n) >> for constant c and no  f(n) is omega (g(n)) or g(n) is O(f(n))

4- big oh of f(n) = 10 n^4 + 5n^2 is O(n^4)

Proof: by the Big-Oh definition, T(n) is O(n^4) if T(n) <= c.N^4="" for="" some="" n ="">= n0 . Let us check this condition: if 10 n^4 + 5 n^2  <=>=>

10 + 5/ n^2 <= c="" therefore,="" the="" big-oh="" condition="" holds="" for="" n ="">= n0 = 1 and c >= 15 (= 10 + 5). Larger values of no result in smaller factors c

(e.G., for n0 = 10  --> 10 * 10^4 + 5*10^2  <= c="" *="" 10^4="" then="" c="">= 100.5 =>and so on) but in any case the above statement is valid.

5- O(1), O(log n), O(n^1/k) (k>1), O(n), O(n log n), O(n^k) like O(n^100) (k > 1),O(2^n), O(n!), O(n^n)

T(n) = 4T (n/4) + 2 sqroot n >> log a to base b = log 4 to base 4 = 1, case 1  O(n^1-E) for E=1/2  => O(n^1/2) = O (sqroot n) Correct

T(n) = 4T (n/4) + 5 n^2, case 1: O(n^1-E) for E=0 or 1 not working, Case 2: Theta (n^1 log^0 n) => Theta (n^2) then T(n) is theta (n^1 log^0+1 n)=nlogn

case 3: omega (n^1+E) for E=1 => omega (n^2)

=>=>