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

* Googmeister:
On Jan 28, 9:13 pm, "sarah" <sarahsmit...@xxxxxxxxx> 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?
.

Relevant Pages

  • Re: Smoke one for my Brother
    ... >and alleged cuddly image, and PLEASE refrain from polluting this ... >thread with politics. ... Out of respect for his brother, I shall further refrain from getting ...
    (alt.smokers.cigars)
  • Re: An schizophrenic called Musatov wants destroy Sci-math
    ... That's very nice of you decent people. ... May I suggest you also refrain ... from polluting sci.math with commentary on Musatov's polluting sci.math? ... "Wovon mann nicht sprechen kann, ...
    (sci.math)