Re: hey help in solving the following recurrence...

* sarah:
On Jan 28, 11:24 pm, Thad Smith <ThadSm...@xxxxxxx> wrote:
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"?
--
Thad

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 should not ask us to do your HOMEWORK.

As it happens you haven't managed to state the complete homework assignment, because the recurrence has a very simple closed form (formula) where it's meaningless to ask about upper and lower asymptotic 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?
.