I need help with the homework in the attached file.

 

 

CSE 2321 MWF 9:10-10:05 Homework 6
Turn In: Hardcopy, at the start of class Friday, March 3rd.
Reminder: Homework should be worked on individually. The hardcopy
you turn in needs to be clean and legible, or it will not be graded. If you are
stuck on a problem, please spend time thinking about the problem and trying
different approaches before seeking help in office hours. If you come to office
hours, you will benefit more if you have already attempted these problems.
1. For each of the following code snippets, find the asymptotic running
time (i.e. Θ). Justify your answer in the same way we did in class: find
an expression for the running time as a function of n, then find a valid
upper and lower bound which differ by only a constant factor.
(a) Func1(n)
s=0
for i = 1 to n2 do
for j = 1 to n2 do
s=s+i+j
return s
(b) Func2(n)
s=0
for i = 1 to n2 do
for j = 1 to i2 do
s=s+i+j
return s
(c) Func3(n)
s=0
for i = 1 to n2 do
for j = 1 to n2 do
for k = 1 to j do
s=s+i+j
return s 1 (d) Func4(n)
s=0
for i = 1 to n2 do
for j = 1 to n2 do
s=s+i+j
for k = n2 + 1 to n3 do
s=s+i+j
return s
(e) Func5(n)
s=0
for i = 1 to n2 do
j=1
while (j < n) do
j =j+5
for k = 1 to j do
s=s+i+j
return s
(f) Func6(n)
s=0
for i = 1 to n2 do
j = 2i
while (j < i4 ) do
s=s+i+j
j = 2j
return s 2 (g) Func7(n)
s=0
i=n
while (i < 5n3 ) do
j = 10n3
while (j > 3) do
s=s+i+j
j = bj/5c
i = 3i
return s
(h) Func8(n)
s=0
for i = 1 to n do
for j = i to n2 do
for k = j to n3 do
s=s+i+j
return s
(i) Func9(n)
s=0
for i = 1 to n/2 do
for j = i to i2 do
s=s+i+j
return s
(j) Func10(n)
s=0
i=1
while (i < n) do
for j = 1 to n do
i=i+1
s=s+i+j
return s 3

Attachments:

• 1493364330-Solutions file 2.docx