Assignment 1
Due September 18, 2019
Provide Asymptotic Analysis for the following programs.
1.
j = 0;
for i = 1 to n by 1 {
j= j+i;
}
m = 0;
for k = 1 to n*n by 1 {
m= m+k;
}
2.
j = 0;
for i = 1 to n by 1 {
j= j+i;
}
m = 0;
for k = 1 to j*j by 1 {
m=m+k;
}
3.
j = 0;
for i = 1 to n by 1 {
for k = 1 to n*n by 1 {
j = j+k;
}
}
4.
j = 0;
for i = 1 to n by 1 {
for k = 1 to (n-i) by 1 {
j = j+k;
}
}
5.
j = n;
while (j >1) {
j = j / 2; integer division
}
6. Tricky problem.
input n;
input m;
while (m > 0) {
t = n mod m;
n = m;
m = t;
}
print n
7. Try running this code (even by hand) for non negative
integer inputs. What is the relationship between the
inputs and the output?