0

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
4
Views
8 Years
Discussion Span
Last Post by iamsmooth
0

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: n/a

0

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

0

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

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.