Algorithms

Classified in Computers

Written at on English with a size of 1.86 KB.

 

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

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  ≤ c.N^4

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)


Entradas relacionadas: