CSE 2331 Homework 2 Winter, 2019
Give the asymptotic running time of each the following functions in Θ no- tation. Justify your answer. (Show your work.)
WRITE YOUR ANSWERS ON A SEPARATE SHEET OF LINED PAPER. DO NOT HAND IN A MARKED UP QUESTION SHEET.
1.
2.
1 2
3 4 5 6 7
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2
3 4 5 6 7 8 9
Func1(n)
s←0; fori←23to⌊n3/2⌋do
for j ← 15 to i2⌊(log5(i))2⌋ do s ← s + i − j;
end end
return (s);
Func2(n)
s←0;
for i ← ⌊n/2⌋ to ⌊n log4(n)⌋ do
for j ← i to ⌊nlog4(n)⌋ do for k ← 3j to 3j + 216 do
s ← s + i − j + k; end
end end
return (s);
Func3(n)
s←0;
fori←7n2 ton3 do √
j←⌊ i⌋;
while (j ≥ 4) do
s ← s + i − j;
j ← j − 17 ; end
end return (s);
Func4(n)
s←0;
for i ← ⌊n/2⌋ to ⌊n3/2⌋ do
for j ← ⌊n/10⌋ to i do for k ← j to i do
s ← s + i − j + k; end
3.
4.
/* Note: Subtraction */
end end
return (s);
1
5.
1 2 3 4 5 6 7 8 9
10 11
1 2 3 4 5 6 7 8 9
10 11
1 2 3 4 5 6 7 8 9
1 2 3
4 5 6 7 8 9
Func5(n)
s←0;
i←29;
while (i < n2) do
j ← 6;
while j ≤ 5n3 do
s ← s + i − j;
j ← 3 ∗ j; end √
i←i+⌈5 n⌉; end
/*Note: Addition*/
6.
return (s);
Func6(n)
s←0;
i←n; √ while (i < ⌊n3
j ← 4;
while (j < 3i) do
s ← s + i − j;
j←j+17; end
i ← 5 ∗ i ; end
return (s);
Func7(n)
s←0; fori←3to⌊nlog3(n)⌋do
/*Note: Addition*/ /* Note: Multiplication */
n⌋) do
7.
8.
j ← i2;
√
while (j >⌈
s ← s + i − j;
j ← ⌊j/7⌋ ; end
end return (s);
Func8(n)
s←0;
i ← ⌊n log9 (n)⌋; while (i > 23) do
/* Note: Division by i
for j ← 62 to ⌊n2 log7(n)/i⌋ do
i⌉ do
/* Note: Division */
s ← s + i − j; end
i ← ⌊i/3⌋ ; end
return (s);
*/
/* Note: Division */
2
9.
10.
1 2 3 4 5 6 7 8 9
10 11
1 2 3 4 5 6 7 8 9
10 11
Func9(n)
s←0;
i ← ⌊√n⌋; while(i>3)do
j ← 5;
while (j < n4) do
s ← s + i − j;
j ← (1.1) ∗ j ; end
i ← ⌊i/12⌋ ; end
return (s);
Func10(n)
s←0;
i←25;
while (i < n3) do
j ← 6;
while (j < i2) do
s ← s + i − j; √
j←j+⌊ i⌋; end
i ← 7 ∗ i ; end
return (s);
/* Note: Multiplication */ /* Note: Division */
3
/*Note: Addition*/ /* Note: Multiplication */