Question

@computer science how much is the executin time of his algorithm in function of n
k:=1;
while k<=n do
begin
j:=1;
while j<=k do
begin
s:=s+1;
j;=j+1;
end;
k:=2*k
end

Answer 1

easy

Answer 2

induction on n ≥ 0 that for every a = 1, and all 0 ≤ j ≤ n, n. ∑ i=j ... ∑n i=1 i k ≤ nk. (n + 1)/2. 22. Prove by induction on n ≥ 0 that n. ∑ i=1. 1 i2. < 2 − ...#
: An array of n elements, in which half are ' a 's and the other half are ' b 's. ... findingA_MC(array A, n, k) begin i=1 repeat Randomly select one element ... This algorithm does not guarantee success, but the run time is fixed. .... If we fix all rj except r1, the equality holds for at most one of the two choices for r_1\in \{0,1\} . ...
#

Answer 3

k := 1;
while k <= n do
begin
j := 1;
while j <= k do
begin
s := s + 1;
j := j + 1;
end;
k := k * 2;
end;

you want the computational complexity? it's O(n^2)

Answer 4

yes but why