1. Suppose we have determined that this loop is where our algorithm does the mos

Question

1. Suppose we have determined that this loop is where our algorithm does
the most work:
for(int i = 0; i < N; ++i)
for(int j = 0; j < N; ++j)
for(int k = 0; k < N ++k)
a[i][j] = b[i][j] *b[i][k];
How would we express the running time in Big Oh notation?
a-You are given the information that the running time of one algorithm
is proportional to N logN and the running time of another algorithm is
proportional to N3. What does that statement imply about the relative
performance of the algorithms?
b- For what values of N is 10N logN > 2N2?

Explanation / Answer

The running time would be O(N3)

because the instruction a[i][j] = b[i][j] *b[i][k]; is carried k*j*i times = N3 times

a) log(N) rises slower than N

so Nlog(N) < N2 <N3

The algorith with N3 will be slower than Nlog(N)

b) 10N logN > 2N2

10logN > 2N

5logN > N

n>2

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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