time complexity

[pankajkumar]

time complexity of-

for i:= 1 to n do

for j:= i+1 to n do

for k:= j+1 to n do

if P1/W1 is less than P2/W2...less than Pn/Wn, prove greedy generate optimal solution to knapsack prob.

[EdEarl]

You haven't explained what i, j an k represent. I assume they are subscripts of three different kinds of things that may be put into the knapsack. Suppose there are M things that may be put in the knapsack, and there are differing amounts of each of the M things, i.e., n_M. When M > 3, you need subscripts i, j, k, l, ..., and loops for each one.

 

If M and n_M are large enough, not even the fastest super computers can solve the problem quickly.

Edited May 29, 2013 by EdEarl

[D H]

 

time complexity of-

for i:= 1 to n do

for j:= i+1 to n do

for k:= j+1 to n do

if P1/W1 is less than P2/W2...less than Pn/Wn, prove greedy generate optimal solution to knapsack prob.

Is this one question or two? It looks like two separate questions to me, one about the time complexity of that loop construct, the other about the knapsack problem. If that's the case, the first question is easy. How many times is the body (not shown) of the innermost loop going to be executed?

 

Regarding the second question, if it is a second question: You need to give us a lot more to go on.

 

 

Note very well: We do notdo your homework for you at this site. Instead we help you do your own homework. This means you need to show some work, and also show some respect by not writing so vaguely.