2

how can we tell whether the obtaining time complexity for an algorithm is in best case or worst case or an average case? example if we get time complexity as t(n) = 2n^2 + 3n -1, how to estimate the best or worst or average cases?

vamsi
  • 29
  • 1
  • 2
  • in merge sort the time complexity in avg case is n^2, in best case it is n and in worst case it is n^2. how can we say like that. what is the procedure? – vamsi Sep 16 '11 at 16:12
  • 1
    I think you want to say bubble sort and not merge sort. Anyway it's because it depends on the input, the worst case is when the list is reversed, the best is when it's already sorted, the average is given a random premutation the probability of complexity is still O(n^2) – Ricky Bobby Sep 16 '11 at 16:17
  • i am not getting clarity. please tell me some more clearly that if we get t(n) = n^2+n, what is the average case? is it sufficient to tell or do we require some more? – vamsi Sep 16 '11 at 16:22

4 Answers4

2

first note : t(n) = 2n^2 + 3n -1 will always be a big O(n^2) in worst, best and average case.

In some cases the complexity depends on the input of your algorithm, in these cases usually people calculate the complexity in worst case.

But when you think worst case is not relevant and too restrictive, you do an average case analysis or an amortized analysis. For example if an algorithm works in O(n) for (1-1/n)% of his inputs and O(n^2) for (1/n)%, you don't want to say it's O(n^2), and give the average complexity that will be more like O(n). But the worst case can still happen.

Look at this post for more detail on average case analysis and amortized analysis.

Difference between average case and amortized analysis

and the wikipedia's articles :

Community
  • 1
  • 1
Ricky Bobby
  • 7,490
  • 7
  • 46
  • 63
  • i am not getting clarity. please tell me some more clearly that if we get t(n) = n^2+n, what is the average case? is t(n) is sufficient to tell that in which case it is or do we require some more? – vamsi Sep 16 '11 at 16:28
  • i am not getting clarity. please tell me some more clearly that if we get t(n) = n^2+n, what is the average case? is it sufficient to tell or do we require anything else? – vamsi Sep 16 '11 at 16:34
1

You can only tell that by carefully examining the algorithm.

If you know that exactly t(n)=2n^2+3n-1, then t(n)=O(n^2) and that's the best, the worst and consequently the average time complexity.

Karoly Horvath
  • 94,607
  • 11
  • 117
  • 176
  • i am not getting clarity. please tell me some more clearly that if we get t(n) = n^2+n, what is the average case? is t(n) sufficient to tell or do we require anything else – vamsi Sep 16 '11 at 16:35
  • if you have an exact equation the best, worse and average cases are all the same. – Karoly Horvath Sep 16 '11 at 16:41
0

enter image description here >>Bast Case:

If you are finding the Best case Complexity then you check image and following statement.

T(n)= c1n+c2(n-1)+c4(n-1)+c5(n-1)+c8(n-1)
      (c1+c2+c5+c8)n-(c2+c4+c5+c6)

The Maximum Power of n is 1, so we are say tha Best Case Complexity is Insertion Sort O(n).

>>Worst Case:

If you are finding the Worst case Complexity then you check image and following statement.

T(n)= c1n+c2(n-1)+c4(n-1)+c5(n(n+1)/2)+c6(n(n-1)/2)+c7(n(n-1)/2)+c8(n-1)
      (c5/2 + C6/2 +C7/2)n^2 +(c1+c2+c4+ c5/2 -C6/2 -C7/2+ c8)

The Maximum Power of n is 2, so we are say tha Best Case Complexity is Insertion Sort O(n^2).

Pengyy
  • 37,383
  • 15
  • 83
  • 73
Zeeshan
  • 1
  • 2
0

That simplifies to O(2n^2) or just merely O(n^2). You remove all the other elements because it simplifies.

This is known as Big O notation. This is simply the worst case time. THe others all are irrelevant for the most part.

apollosoftware.org
  • 12,161
  • 4
  • 48
  • 69
  • i am not getting clarity. please tell me some more clearly that if we get t(n) = n^2+n, what is the average case? is t(n) sufficient to tell or do we require some more? – vamsi Sep 16 '11 at 16:34