Re: time complexity.. again there was some mistake.
- From: Proginoskes <CCHeckman@xxxxxxxxx>
- Date: Mon, 17 Sep 2007 06:14:13 -0000
On Sep 16, 5:22 pm, dondora <koni...@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.
(Let's trim those ----------- lines, okay? Usenet only supports a
width of 80 characters!)
----------------------------------------------------------------------
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.
The number of times that <body of the while loop> is executed is
actually
lg 1 + lg 2 + lg 3 + ... + lg n = lg (n!)
(where lg is log base 2, of course). There are asymptotic formulas for
n! available --- Sterling's Approximation, for instance --- which are
available at MathWorld or even Wikipedia.)
--- Christopher Heckman
.
- References:
- time complexity.. again there was some mistake.
- From: dondora
- time complexity.. again there was some mistake.
- Prev by Date: Re: google-plex and beyond
- Next by Date: Re: Ramadan
- Previous by thread: time complexity.. again there was some mistake.
- Next by thread: SMARTboard Board Annoying Text Stretching
- Index(es):
Relevant Pages
|
