Given a formula in propositional logic with $100$ variables. We know that there can be no SAT-checking provably faster than $O(2^n)$, unless P=NP. Now let's say I could find an algorithm which does SAT-solving provably in $O(2^{{n\choose3}/10^6})$. Now this algorithm is asymptotically poor, but is provably optimal till $n=1000$.
Question: Are there such algorithms in literature ? i.e asymptotically sub-optimal but provably optimal in a certain range ?
Edit : I mistakenly wrote $O(2^{{n\choose3}/10^6})$ as $O({{n\choose3}/10^6})$. Thanks @Yonatan N