944,168 Members | Top Members by Rank

Software Development > Computer Science > Can someone help explain asymptotic notation in regards to algorithms for me?
Ad:
Permalink
Oct 13th, 2009
0

Can someone help explain asymptotic notation in regards to algorithms for me?

Expand Post »
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!
Similar Threads
Reputation Points: 10
Solved Threads: 0
Light Poster
iamsmooth is offline Offline
49 posts
since Jul 2009
Permalink
Oct 13th, 2009
0
Re: Can someone help explain asymptotic notation in regards to algorithms for me?
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.
Last edited by BestJewSinceJC; Oct 13th, 2009 at 5:24 am.
Reputation Points: 874
Solved Threads: 352
Posting Maven
BestJewSinceJC is offline Offline
2,758 posts
since Sep 2008
Permalink
Oct 13th, 2009
3
Re: Can someone help explain asymptotic notation in regards to algorithms for me?
Yes, read through the Time Complexity of Algorithm thread. It's a very old thread and has practical and theoretical answers.
Team Colleague
Reputation Points: 1135
Solved Threads: 173
Super Senior Demiposter
Rashakil Fol is offline Offline
2,480 posts
since Jun 2005
Permalink
Oct 13th, 2009
0
Re: Can someone help explain asymptotic notation in regards to algorithms for me?
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
Reputation Points: 10
Solved Threads: 0
Light Poster
iamsmooth is offline Offline
49 posts
since Jul 2009

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in Computer Science Forum Timeline: Algorithm issues
Next Thread in Computer Science Forum Timeline: Research on the use of graphics to replace typed passwords.





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC