What is the time complexity of these algorithms, in terms of n? [ Sum += y is a
ID: 3771445 • 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.] [Only write answers, NO explanations]
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 and 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 and analysis algorithm
Explanation / Answer
Answer:
1)
The time complexity of the first code is given as,
Since, the loop does not start from the initial value 1. So, the loop values are given as,
First loop can be executed if there are no internal loops: log(n)-5
Next it contains second loop that is executed for n-5 times.
Since, the second loop lies inside the first loop, so the overall execution of the external becomes the time complexity of the algorithm.
So, the number of iterations is given as,
Therefore, the time complexity is .
3)
The modifications of the x value does not affect the value of x at while loop. The third while loop will be executed only once since, the x in not incremented inside the loop.
Finally, value of x is dependent on the value of k.
So, the overall execution of loops is given as, n2.
Therefore, the time complexity is O(n2).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.