Member Avatar for iamsmooth

I'm not very math profficient yet, since I haven't taken enough Math classes at school, but we're covering asymptotic notation and running times of algorithms in class, which seems pretty mathy (yes mathy is a word).

Anyways, first, I need to clarify: upper/lower bounds refers to max/min cost of an algorithm, right? i.e. if we have 1 < t < 10, lower bounds is 1, and upper bounds is 10?

Secondly, I want to clarify if what I think is true: there exists many different notations, big-o, little-o, theta, etc, and all of it describes the run time differently. I think big-o describes the upper bounds of an algorithm's cost or something? With that, how do you describe and analyze an algorithm? In class, we get asked what the worst case run time is of something, and the answer is always theta of 1, or theta of something. How can I tell?

Lastly, what does amortized cost mean?

Thanks to anyone who replies!

  • 3 Contributors
  • 3 Replies
  • 134 Views
  • 21 Hours Discussion Span
  • Latest Post Latest Post by iamsmooth
Member Avatar for BestJewSinceJC

I'm not trying to be rude, but Narue already had a pretty good explanation of at least one of your questions in a similar thread that was created in this forum recently (it should still be on the first page).

(The question):
"I think big-o describes the upper bounds of an algorithm's cost or something? With that, how do you describe and analyze an algorithm?"

As for amortized cost, amortized analysis deals with considering the worst case running time of a sequence of M operations. If you want an example of why this is useful look into splay trees big-oh cost versus their amortized cost.

Edited by BestJewSinceJC because: n/a
Member Avatar for Rashakil Fol

Yes, read through the Time Complexity of Algorithm thread. It's a very old thread and has practical and theoretical answers.

Member Avatar for iamsmooth

Sorry, didn't see that because we never used the term "time complexity" in class. But thanks for directing me to such an awesome thread :D

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.