Algorithms

Homework

1. Which of the following statements are true, which are false? Prove your answers.
i. n26 0 (n3) .7
ii. n360(n2)~
iii. 2’”’60(2″)
iv. (n +1)!e 0(n!)
v. for any function f :IN -> 112*, {me-om =: [f(n)]260(n2)
vi. for any functionf :N -> R*,f(n)60(n) =9 2″”600″)
2. Analyze the running time for the following two programs, expressing the results in O-notation.
i, function max ( i, n: integer ) : integer;
var
ml, m2: integer;
begin
if n = I then
return (A[i])
else begin
ml := max(t’, n div 2);
m2 := max(i+n div 2. n div 2);
if ml < m2 then
return (m2)
else
return (m I)
end
end
ii. procedure mystery ( n: integer
var
x, count: integer;
begin
count := 0;
x := 2;
while 1: < n do begin
x := 2 * x;
count := count + 1
end;
writeln(count)
end

 

PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET A GOOD DISCOUNT 🙂