Для каждой из приведенных программ и функций оцените время ее работы а) for i in range (n) j = 0 while j * j < i: j +- один b) for i in range (n) j = один

а) Внутренний цикл выполняется не больше C_1 + C_2 sqrt(i) элементарных операций, так что всё вместе не больше

C_0 + sum_{i = 0}^n (C_1 + C_2 sqrt(i)) =

= C_0 + C_1 n + C_2 int_0^{n + 1} sqrt(x) dx =

= C_0 + C_1 n + C_2 2/3 * x^{3/2} = O(x^{3/2})

б)Внутренний цикл работает не больше C_1 + C_2 [log_2 i] элементарных оп...