CODEWITHSUNDEEP
algorithmbig-o
Luke12
Luke12

Reputation: 137

Big O algorithms minimum time

I know that for some problems, no matter what algorithm you use to solve it, there will always be a certain minimum amount of time that will be required to solve the problem. I know BigO captures the worst-case (maximum time needed), but how can you find the minimum time required as a function of n? Can we find the minimum time needed for sorting n integers, or perhaps maybe finding the minimum of n integers?

Upvotes: 3

Views: 136

Answers (1)

stinepike
stinepike

Reputation: 54722

what you are looking for is called best case complexity. It is kind of useless analysis for algorithms while worst case analysis is the most important analysis and average case analysis is sometimes used in special scenario.

the best case complexity depends on the algorithms. for example in a linear search the best case is, when the searched number is at the beginning of the array. or in a binary search it is in the first dividing point. in these cases the complexity is O(1).

for a single problem, best case complexity may vary depending on the algorithm. for example lest discuss about some basic sorting algorithms.

  1. in bubble sort best case is when the array is already sorted. but even in this case you have to check all element to be sure. so the best case here is O(n). same goes to the insertion sort
  2. for quicksort/mergesort/heapsort the best case complexity is O(n log n)
  3. for selection sort it is O(n^2)

So from the above case you can understand that the complexity ( whether it is best , worst or average) depends on the algorithm, not on the problem

Upvotes: 2

Related Questions