If an algorithm worst case running time is 6n^4 2, and its best case running time is 67 6n^3. What is the most appropriate asymptotic notation.

I'm trying learn about Big O notation.

is it Θ(n^2) ?

CodePudding user response：

Essentially, Big-Oh time complexity analysis is defined for best case, worst case or average number of operations algorithm performs. "is it Θ(n^2) ?" So, you should specify which case are you looking for? Or do you mean to say is it Θ(n^2) for all cases? (which is obviously not correct)

Having said that, we know that algorithm performs 6n^4 2 operations in worst case. So it has Θ(n^4) worst case complexity. I've used theta here because I know exactly how many operations are going to be performed. In the best case, it performs 67 6n^3 operations. So it has Θ(n^3) time complexity for the best case.
How about average time complexity? Well, I can't know as long as I am not provided with the probability distribution of the inputs. It's maybe the case that best-case-like scenario rarely occurs and average time complexity is Θ(n^4), or vice versa. So we cannot directly infer the average time complexity from the worst/best case time complexities as long as we are not provided with input probability distribution, the algorithm itself or the recurrence relation. (Well, if best and worst time complexities are the same, then of course we can conclude that average time complexity is equal to them)

If algorithm is provided, we can calculate average time complexity making some very basic assumptions on the input (like equally likely distribution etc.). For example in linear search, best case is O(1). Worst case is O(n). Assuming equally likely distribution, you can conclude that average time complexity is O(n) using expectation formula. [sum of (probability of input i) * (number of operations for that input)]

Lastly, your average time complexity CANNOT be Θ(n^2) because your best and worst time complexities are worst than quadratic. It doesn't make sense to wait this algorithm perform n^2 operations in average, while it performs n^3 operations in best case.

Time complexity for best case <= time complexity for average <= time complexity for worst case