Re: time complexity

On Sun, 16 Sep 2007 15:09:54 +0200, dondora <koninja@xxxxxxxxxxx> wrote:

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.

I didn't checked the maths, but the result (n log(n)) is OK.
How did I find this ?
Well, the while loop is executed k = log(n) times for each body of the for loop and the for loop is executed n times.
So the total times is something like n*k.

--
Hypocoristiquement,
Jym.
.

Relevant Pages

  • Re: Newbie: whats Ruby idiom for word-by-word input?
    ... If you want to read to word boundaries only it becomes more difficult. ... you can use #getc and implement the word matching logic ... anyway the nested loop approach yields the proper result (aka sequence ...
    (comp.lang.ruby)
  • Re: How to break a while loop inside a switch statement?
    ... You have never needed out of a nested loop? ... There are times when a simple nested loop of 2-4ish levels is easier to ... read and maintain than having each loop level in its own method. ... latter might often require extra fields or parameters to be introduced ...
    (comp.lang.java.programmer)
  • Re: How to break a while loop inside a switch statement?
    ... You have never needed out of a nested loop? ... There are times when a simple nested loop of 2-4ish levels is easier to ... read and maintain than having each loop level in its own method. ... latter might often require extra fields or parameters to be introduced ...
    (comp.lang.java.programmer)
  • Re: resolve single line with multiple items into mutliple lines, single items
    ... This automatically leads to a nested loop, which you can use nicely to ... Recursion and loops are two different ways to achive the same result: ... repeating the execution of some code with modified data. ...
    (comp.lang.perl.misc)
  • Re: problems with throw/catch (newbie)
    ... Ruby force you to use catch/throw (which intuitively seems like ... but the reason I asked is that I anticipate having to break ... Interestingly I cannot remember having to break from a nested loop. ...
    (comp.lang.ruby)