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: Simple Help with loops
    ... file=input('What is the name of the 2x2 matrix file to load? ... What can I do so that I can load any file in the correct directory the user inputs? ... The real question is whether he or she would consider this to be a nested loop. ...
    (comp.soft-sys.matlab)
  • 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)