COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### hey help in solving the following recurrence...

• Email
• Follow

```hi can yu hep me solve the following recurrence,

T(n)=T(n-1)+lgn

T(2) and T(1) are constants...

thnks all,

```
 0
Reply sarahsmith11 (3) 1/29/2007 2:13:32 AM

See related articles to this posting

```hi,,

I need to find the asymptotic upper and lower bounds for T(n) in the
following recurrences.
lgn= log(n) to the base 2.

sorry shud have been more clear....

> sarah wrote:
> > hi can yu hep me solve the following recurrence,
>
> > T(n)=T(n-1)+lgn
>
> > T(2) and T(1) are constants...What do you mean by "solve"?  What is "lgn"?
>
> --

```
 0
Reply sarahsmith11 (3) 1/29/2007 2:27:57 AM

```* sarah:
>> sarah wrote:
>>> hi can yu hep me solve the following recurrence,
>>> T(n)=T(n-1)+lgn
>>> T(2) and T(1) are constants...What do you mean by "solve"?  What is "lgn"?
>> --
>
> hi,,
>
> I need to find the asymptotic upper and lower bounds for T(n) in the
> following recurrences.
> lgn= log(n) to the base 2.
>
> sorry shud have been more clear....

Yes, and you should NOT TOP-POST (I've rearranged the above) and you

As it happens you haven't managed to state the complete homework
assignment, because the recurrence has a very simple closed form
bounds, especially "the".  Perhaps the missing part is a requirement
that you find upper and lower asymptotic bounds for an approximation of
that function in terms of only arithmetic, logarithms and exponentials.
IIRC the hard part of that is discussed in Knuth's TAOCP volume I.

Start by finding the closed form formula for the recurrence: that
shouldn't be hard, at least not if you remember that log(x)+log(y) =
log(x*y).

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
```
 0
Reply alfps (7389) 1/29/2007 3:21:05 AM

```On Jan 28, 9:13 pm, "sarah" <sarahsmit...@gmail.com> wrote:
> hi can yu hep me solve the following recurrence,
>
> T(n)=T(n-1)+lgn
>
> T(2) and T(1) are constants...

If you expand it out (assuming T(0) = 0):

T(n) = T(n-1) + lg n
= T(n-2) + lg(n-1) + lg n
...
= lg 1 + lg 2  + ... + lg n
= lg (n!)
= Theta(n log n)

```
 0
Reply googmeister (267) 1/29/2007 3:28:15 AM

```sarah wrote:
>
> hi can yu hep me solve the following recurrence,
>
> T(n)=T(n-1)+lgn
>
> T(2) and T(1) are constants...
>
> thnks all,

We probably could, if it wasn't homework, and if you used some sort
of known language to ask.  Consider defining yu, hep, lgn, thnks.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

```
 0
Reply cbfalconer (19194) 1/29/2007 3:40:23 AM

```* Googmeister:
> On Jan 28, 9:13 pm, "sarah" <sarahsmit...@gmail.com> wrote:
>> hi can yu hep me solve the following recurrence,
>>
>> T(n)=T(n-1)+lgn
>>
>> T(2) and T(1) are constants...
>
> If you expand it out (assuming T(0) = 0):
>
> T(n) = T(n-1) + lg n
>        = T(n-2) + lg(n-1) + lg n
>        ...
>        = lg 1 + lg 2  + ... + lg n
>        = lg (n!)
>        = Theta(n log n)

Why do you think it helps the OP to do his (or perhaps her) homework?

In the future, please refrain from those urges to show off.

You're only showing that (1) you haven't grasped the nature of learning,
(2) you haven't grasped the cost to society of cheating, and (3) you
regard even trivial questions as this as sufficiently hard that you
think you can earn points by providing solutions; in addition, you're
polluting the newsgroup with a posting of no value to most readers.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
```
 0
Reply alfps (7389) 1/29/2007 3:46:04 AM

```sarah wrote:
> hi can yu hep me solve the following recurrence,
>
> T(n)=T(n-1)+lgn
>
> T(2) and T(1) are constants...

What do you mean by "solve"?  What is "lgn"?

--
```
 0