well, I think the result is correct.

dondora 写道:

hi there.

this is my homework. I've been trying to get some result but things

haven't been gone well.

Those are the nested loop. And What I have to do is to get time

complexity T(n) of the nested loop assuming n=2^k.

---------------------------------------------------------------------------------------------------------

for(i = 0; i<=n; i++) {

j = n;

while( j>= 1) {

<body of the while loop // Needs ϴ(1)

j = j/2;

}

}

---------------------------------------------------------------------------------------------------------

What I got is T(n) = n{1 + (k+1)(ϴ(1) + 1_} assuming j=n and j=j/2

and ϴ(1) are unit operations.

So I did try to solve my result to get a neat expresion.

that's what I did

n=2^k = lg(n)=k

T(n) = n{1 + (k+1)(ϴ(1) + 1)}

= n{1 + (lg(n) + 1)(ϴ(1) + 1)}

= n{1 + lg(n)ϴ(1) + lg(n) + ϴ(1) + 1} // by distribution law

and

= n{1 + lg(n)ϴ(1) + lg(n) + ϴ(1)}

= n{1 + lg(n)ϴ(1) + ϴ(lg(n))}

= n{1 + ϴ(lg(n)) + ϴ(lg(n))}

= n{ϴ(lg(n)) + ϴ(lg(n))}

= n{ϴ(lg(n))} = nϴ(lg(n)) = ϴ(nlg(n))

is that right? I wanna know where it's right or not.

I guess it has something wrong. So I need your help.

I appreciate your generous help.

ps : don't say to me 'do you own homework'. I already tried many times.