1. Give a big-Oh notation, in terms of n and m, of the running time of the follo

Question

1. Give a big-Oh notation, in terms of n and m, of the running time of the following
procedures, including your explanations:
a. Procedure1(n)
for (i = 0; i < n; i++) {
for (j = n; j > i; j--) {
A[i][j] = j*A[i] + i*B[i];
}
}

b. Procedure2(n, m)
for (i = 0; i < n; i++) {
A[i] = A[i] - B[i];
}
for (i = 0; i < m; i++) {
A[i] = A[i] + B[i];
}

c. Procedure3(n)
for (i = 0; i < n; i++) {
for (j = n; j > 0; j--) {
A[i][j] = j*A[i] + i*B[i];
}
}
for (i = 0; i < n; i++) {
A[i] = A[i] + B[i];
}

d. Procedure4(n)
for i = 1 to log n do
A[i] = A[i] + i

e. Procedure5(n)
for i = 0 to n2 + n do
A[i] = A[i] + i;

f. Procedure6(n)
i = 0;
while (i < 3*n
3 + 200*n2 + 300*n + 10000) {
System.out.print(

Explanation / Answer

a) O(n2)

b) O(m+n)

c)O(n2)

d) O(logn)

e)O(n2)

f)O(n3)

g)O(nlog(n))

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.