0

I understand the worst/avg/best case are used to determine the complexity time of an algorithm into a function but how is that used in asymptotic analysis? I understand the upper/tight/lower bound(big O, big omega, big theta) are used to compare two functions and seeing what it's limit(growth) is in perspective to the other as n increases but i'm having trouble seeing the difference between worst/avg/best case big O and asymptotic analysis. What exactly do we get out of imputing our worst/avg/best case big O into the asymptotic analysis and measuring bounds? Would we use asymptotic analysis to specifically compare two algorithms of worst/avg/best case big O? If so do we use function f(n) for algorithm 1 and g(n) for algorithm 2 or do we have separate asymptotic analysis for each algorithm where algorithm 1 is f(n) and we try to find some c*g(n) such that => f(n) and such that c*g(n) <= f(n) and then do the same thing for algorithm 2. I'm not seeing the big picture here.

3 Answers 3

4

Since you want the big picture, let me try to give you the same.

Asymptotic analysis is used to study how the running time grows as size of input increases.This growth is studied in terms of the input size.Input size, which is usually denoted as N or M, it could mean anything from number of numbers(as in sorting), number of nodes(as in graphs) or even number of bits(as in multiplication of two numbers).

While dealing with asymptotic analysis our goal is find out which algorithm fares better in specific cases.Realize that an algorithm runs on quite varying times even for same sized inputs.To appreciate this, consider you are a sorting machine.You will be given a set of numbers and you need to sort them.If I give yuo a sorted list of numbers, you would have no work, and you are done already.If I gave you a reverse sorted list of numbers, imagine the number of operations you need to do to make the list sorted.Now that you see this, realize that we need a way of knowing what case the input would be?Would it be a best case?Would I get a worst case input?To answer this, we need some knowledge of the distribution of the input.Will it all be worst cases?Or would it be average cases?Or would it mostly be best cases?

The knowledge of the input distribution is fairly difficult to ascertain in most cases.Then we are left with two options.Either we can assume average case all the time and analyze our algorithm, or we could get a guarantee on the running case irrespective of the input distribution.The former is referred to as average case analysis, and to do such an analysis would require a formal definition of what makes an average case.Sometimes this is difficult to define and requires much mathematical insight.All the trouble is worth it, when you know that some algorithm runs much faster on the average case, compared to its worst case running time.There are several randomized algorithms that stand testimony to this.In such cases, doing an average case analysis reveals its practical applicability. The latter, the worst case analysis is more often used since it provides a nice guarantee on the running time.In practice coming up with the worst case scenario is often fairly intuitive.Say you are the sorting machine, worst case is like reverse sorted array.What's the average case?
Yup, you are thinking, right?Not so intuitive.

The best case analysis is rarely used as one does not always get best cases.Still one can do such an analysis and find interesting behavior.

In conclusion, when we have a problem that we wanna solve, we come up with algorithms.Once we have an algorithm, we need to decide if it's of any practical use to our situation.If so we go ahead and shortlist the algorithms that can be applied, and compare them based on their time and space complexity.There could be more metrics for comparison, but these two are fundamental.One such metric could be ease of implementation.And depending on the situation at hand yu would employ either worst case analysis or average case analysis ir best case analysis.For example if you rarely have worst case scenarios, then its makes much more sense to carry out average case analysis.However if the performance of our code is of critical nature and we need to provide the output in a strict time limit, then its much more prudent to look at worst case analysis.Thus, the analysis that you make depends n the situation at hand, and with time, the intuition of which analysis to apply becomes second nature.

Please ask if you have more questions.

To know more about big-oh and the other notations read my answers here and here.

6
  • i'm not sure i understand but do we use asymptotic analysis of either the upper/tight/lower bound on our best/avg/worst case to figure out for example: if our worst case for a given algorithm is O(n^2) maybe its upper bound is a subset of the some other function g(n) that is O(n^3)? When seeing examples of asymptotic analysis it was using a function still with it's constant and lower order terms. With the function we cold tell it's upper, tight, and lower bound or big O, theta, and omega by the basic principle of f(n)<=cg(n), c1*g(1)<=f(n)<=c2*g(n), f(n)=>cg(n). Aug 12, 2013 at 9:13
  • 1
    Uhhh, sorry, what's your doubt?I couldn't get it.
    – Aravind
    Aug 12, 2013 at 9:16
  • So here is an example of an an asymptotic analysis of upper bound based on the function f(n)=3n^4+10n^2+4n+11, 3n^4+10n^2+4n+11 = O(n^4), 3n^4+10n^2+4n+11 = O(n^5), 3n^4+10n^2+4n+11 = O(n^6), How does this relate to a worst case where we have an algorithm with a nested loop that is O(n^2)? I just dont see what do we do with this O(n^2) and the asymptotic analysis in general. From my understanding they are different but also related, you use asymptotic analysis for the worst/avg/best case big O. I just dont see the connection. radford.edu/~nokie/classes/360/order.html Aug 12, 2013 at 9:23
  • 1
    If the function you have described as f(n)=3n^4+10n^2+4n+11 is for the worst case, then yes, this O(N^4) algorithm is worse than O(N^2) in the worst case.This is a subtle point.asymptotic analysis is just a mathematical tool to analyze growth of functions.You can use it for best case/worst case/average case.
    – Aravind
    Aug 12, 2013 at 9:28
  • 1
    Also if you want to have an extended discussion it's best to move over to chat.chat.stackoverflow.com/rooms/35260/asymptotic-complexity
    – Aravind
    Aug 12, 2013 at 9:29
1

The Wikipedia article on quicksort provides a good example of how asymptotic analysis is used on best/average/worst case: it's got a worst case of O(n^2), an average case of O(n log n), and a best case of O(n log n), and if you're comparing this to another algorithm (say, heapsort) you would compare apples to apples, e.g. you'd compare quicksort's worst-case big-theta to heapsort's worst-case big-theta, or quicksort's space big-oh to heapsort's space big-oh.

You can also compare big-theta to big-oh if you're interested in upper bounds, or big-theta to big-omega if you're interested in lower bounds.

Big-omega is usually only of theoretical interest - you're far more likely to see analysis in terms of big-oh or big-theta.

2
  • I'm not sure i understand. When we get the big O of two algorithms, where both algorithms have a nested loop resulting in O(n^2), what is there to compare using asymptotic analysis. Also when i've see asymptotic analysis it was using a function still with it's constant and lower order terms. With the function we cold tell it's upper, tight, and lower bound big O. But again how do we use the best/avg/worst case big O in asymptotic analysis if two algorithms are the same big O for a worst case? What is there to compare... i'm jut not seeing what we are trying to do. Aug 12, 2013 at 9:01
  • @user2644819 If two algorithms have the same asymptotic complexities then there's nothing to compare Aug 12, 2013 at 13:05
0

What exactly do we get out of imputing our worst/avg/best case big O into the asymptotic analysis and measuring bounds?

It just gives an idea when you are comparing different approach for some problem. This will help you in comparing different approaches.

Would we use asymptotic analysis to specifically compare two algorithms of worst/avg/best case big O?

Generally only worse case gets more focus, compared to Big Omega and theta. Yes, we use function f(n) for algorithm 1 and g(n) for algorithm. And these functions are Big O of their respective algorithms.

Not the answer you're looking for? Browse other questions tagged or ask your own question.