Derive the worst-case run-time of the given algorithms (as a function of n). You

Question

Derive the worst-case run-time of the given algorithms (as a function of n). You must formally derive the run-times (merely stating run-times or high level explanation of run-time do not suffice).

1. Derive the worst-case run-time of the given algorithms (as a function of n). You must formally derive the run-times (merely stating run-times or high level explanation of run-time do not suffice) (a) for i in the range [1, n] for j in the range [1, n*i] CONSTANT OPERATIONS (b) r=0; for i in the range [1, n] f for j in the range [i, n] l for k in the range [1, j-i] rtt for j in range [1, i] 1 Constant Number of Operations

Explanation / Answer

Solution:

a)

There are two loops in the given problem, the inner loop is running n*i number of times for every time the outer loop is executing

so, at i= 1 the inner loop will be running n*1= n number of times

and at i= 2 the inner loop will be running n*2= 2n number of times

similarly at i= n the inner loop will be runing n*n= n^2 times

the effectgive running of the loops will be

n+2n+3n+.....+n^2

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

=> n * (n(n+1)/2)= O(n^3)

b)

There are three loops in the gfiven code snippet and all are nested

at i= 1, j= 1,

the inner most loop will be running 0 number of times

similarly at i= 1, j=2, the inner loop will be running 1 number of times

i=1, j=3, the inner loop will be running 2 number of times.

similarly at i= 1, j= n, the inner most loop will be running n number of times

so the effective running at i= 1 will be

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

now the outer most loop is running n number of times

this means the final effective running of the given code snippet will be n*n^2= n^3

So the final time complexity will be O(n^3).

c)

There is a trick here,

the outer loop is jumping as 1, 2, 4, 8, 16, and so on

but at the same time it is running till 2^n which effectively results in running n number of times

since, log2 2^n= n

and the inner loop is running i number of times

so the effective runinng will be

T(n)= O(n^2).

I hope this helped you, please don't forget to give a thumbs up, ask your doubts in the comment section.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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