Show the time complexity of the following algorithms in terms of big-O. Assume \

Question

Show the time complexity of the following algorithms in terms of big-O. Assume "print" is a constant time operation. Your big-O analysis should be as tight as possible. (i.e.,try to make it big-O complexity)
1) k = 1;
for ( i = 0; i < n; i++){
for ( j = 0; j < n; j = j + k)
print(A[j]);
k = k * 2;
}

2) for ( i = 1; i <= n; i++)
for ( j = 0; j < n; j = j + i)
print(A[j]);

You can assume n to be a power of 2. You might want to work them on an exmaple array of size 8. Writing the time as a summation of mathematical series first and the bounding it might work.

Explanation / Answer

1)

the for loop for the 'i' will run n times.

The for loop for j will run log(n) times, because each time k doubles.

So the total time complexity is: O(n*log(n))

2)

For each value of i, the inner loop will be run (n/i) times.

So the complexity is:

(n/1) + (n/2) + (n/3) + ... + (n/n) =

n(1 + 1/2 + 1/3 + ... + 1/n)

and we know that:

(1 + 1/2 + 1/3 + ... + 1/n) ~ log(n)

So the time complexity is:

O(n*log(n))

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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