467,188 Members | 1,426 Online
Bytes | Developer Community
Ask Question

Home New Posts Topics Members FAQ

Post your question to a community of 467,188 developers. It's quick & easy.

time complexity

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.

Sep 16 '07 #1
  • viewed: 2518
Share:
1 Reply
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.
Sep 17 '07 #2

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

3 posts views Thread by Edg Bamyasi | last post: by
25 posts views Thread by Neil Ginsberg | last post: by
9 posts views Thread by davide.sammartino@gmail.com | last post: by
26 posts views Thread by Lionel B | last post: by
3 posts views Thread by youtoo | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.