# Asymptotically Optimal Algorithms [closed]

I am confused how to check if an algorithm I made is asymptotically optimal.

At the very least, the running time is constant at O(4). This is because you will need to check at least 4 names.

At the very most, the running time is linear at O(n). This is from n + n + n/2 + n/2 + n/4 + n/4 + .... = 2n * (1 + 1/2 +...) < 2n. As we ignore constants its just O(n).

I checked on Wiki and it said that the algorithm should perform at worst a constant factor of the best algorithm. But if you invented an algorithm then how do I figure this out?

• Some details are missing here (such as the problem itself you're trying to solve), but they don't seem important. Can you rephrase your question to include only the salient information, yet be completely comprehensible? Commented Mar 10, 2017 at 18:36
• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! Commented Mar 10, 2017 at 19:52

We usually only care about the worst-case complexity of algorithms. An $O(n)$ algorithm is usually asymptotically optimal (assuming $n$ is the input size), since most functions require you to read the entire input in some cases.
Another example in which you can prove asymptotic optimality is comparison-based sorting algorithms. A comparison-based sorting algorithm is a sorting algorithm whose only access to the data is a comparison oracle, which compares to data items. Any such algorithm must make $\Omega(n\log n)$ oracle queries in the worst case. Therefore a comparison-based sorting algorithm running in time $O(n\log n)$ is asymptotically optimal.
• You would need a matching $\Omega(n)$ lower bound, but these are often not hard to prove. Commented Mar 10, 2017 at 18:58