2
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Mar 10, 2017 at 18:36
  • $\begingroup$ 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! $\endgroup$
    – Raphael
    Commented Mar 10, 2017 at 19:52

1 Answer 1

1
$\begingroup$

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.

In most cases, however, we cannot prove that a given algorithm running in superlinear time is optimal, since we don't know how to prove running time lower bounds on general computation models. However, in some cases we can prove such lower bounds conditionally, that is, assuming some widely believed hypothesis. This is known as fine-grained complexity theory, and it indicates (conditionally) that the best algorithms for many problems are indeed asymptotically optimal.

$\endgroup$
10
  • $\begingroup$ But how would I know if my algorithm is 'best' if it is an undefined problem e.g. not a sort. It could be a search algorithm for example in a 3-D space. If you found the value you wanted in the first pass then that would be the 'best' solution no? $\endgroup$ Commented Mar 10, 2017 at 18:55
  • $\begingroup$ You wouldn't know in general, unless your algorithm happens to run in linear time, and the problem is such that the output potentially depends on the entire input. $\endgroup$ Commented Mar 10, 2017 at 18:56
  • $\begingroup$ So if I know for sure my algorithm runs in O(n) I can assume it is asymptotic optimal? How would I argue this is true? $\endgroup$ Commented Mar 10, 2017 at 18:57
  • $\begingroup$ You would need a matching $\Omega(n)$ lower bound, but these are often not hard to prove. $\endgroup$ Commented Mar 10, 2017 at 18:58
  • $\begingroup$ Can you kindly give me an example or point me to an example please? $\endgroup$ Commented Mar 10, 2017 at 19:04

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