What is the time complexity of these algorithms, in terms of n? [ Sum += y is a
ID: 3771130 • Letter: W
Question
What is the time complexity of these algorithms, in terms of n?
[ Sum += y is a short form notation for Sum = Sum + y. gcd(m,n) is the greatest common divisor of m and n. For example, gcd(3,6) = 3.]
int j = 5
while (j < log n) {
int k = 5
while (k < n) {
Sum += a[j]*b[k]
k = k^1.3 }
j = 1.3 * j }
for (int i = 1 to n) { for (int j = i to n) {
for (int k = j to n) { Sum += a[i]*b[j]*c[k]
}
If (gcd(i,j) == 1) {
j=n }
} }
For (int j = 1 to n) { For (int k = j to n)
{
x=k
While (x < n) { Sum +=
a[j]*b[k]*c[x]
If (x % 3 == 0)
{
} }
x=n+1 }
x=x+1 }
subject
design analysis algorithm
int j = 5
while (j < log n) {
int k = 5
while (k < n) {
Sum += a[j]*b[k]
k = k^1.3 }
j = 1.3 * j }
for (int i = 1 to n) { for (int j = i to n) {
for (int k = j to n) { Sum += a[i]*b[j]*c[k]
}
If (gcd(i,j) == 1) {
j=n }
} }
For (int j = 1 to n) { For (int k = j to n)
{
x=k
While (x < n) { Sum +=
a[j]*b[k]*c[x]
If (x % 3 == 0)
{
} }
x=n+1 }
x=x+1 }
subject
design analysis algorithm
Explanation / Answer
Leftmost has time complexity O(n2) because there are two nested loops each running fo length O(n)
middle has tme complexity O(n3) because there are three nested loops each running to length O(n)
rightmost has time complexity O(n3) because there are three nested loops each running to length O(n)