I think the question needs to be sharpened to exclude algorithms that compute (or even involve) combinatorially complex structures. For example, the convex hull of $n$ points in $\mathbb{R}^d$ has size $\Theta(n^{\lfloor d/2 \rfloor})$ for fixed $d$. There is an asymptotically optimal algorithm (due to Chazelle (1)) to compute this hull in time $O( n \log n + n^{\lfloor d/2 \rfloor} )$. So one could exceed any power of $n$ in the time complexity by selection of a sufficiently large $d$.

So you need to specify that the algorithm is a decision procedure, outputting only one bit, Yes or No. But even here, there is no upper bound on the "worst" algorithm time complexity.

Again consider the convex hull in $\mathbb{R}^d$, $d$ fixed, and ask: (a) Is the hull simplicial? or (b) Does the hull have exactly $F$ facets? Jeff Erickson showed (2) that, even for these decision questions, $\Omega( n \log n + n^{\lceil d/2 \rceil -1} )$ time is needed, matching the known upper bounds for odd $d$.

---

(1) Bernard Chazelle. "[An optimal convex hull algorithm in any fixed dimension][1]." _Discrete & Computational Geometry_ Volume 10, Number 1, 377-409

(2) Jeff Erickson. "New Lower Bounds for Convex Hull Problems in Odd Dimensions." SIAM J. Comput., 28 (1995) 1-9.

---

  An irrelevant aside: I coauthored an algorithm with time complexity $O(n^{42})$. :-)

I think the question needs to be sharpened to exclude algorithms that compute (or even involve) combinatorially complex structures. For example, the convex hull of $n$ points in $\mathbb{R}^d$ has size $\Theta(n^{\lfloor d/2 \rfloor})$ for fixed $d$. There is an asymptotically optimal algorithm (due to Chazelle (1)) to compute this hull in time $O( n \log n + n^{\lfloor d/2 \rfloor} )$. So one could exceed any power of $n$ in the time complexity by selection of a sufficiently large $d$.

So you need to specify that the algorithm is a decision procedure, outputting only one bit, Yes or No. But even here, there is no upper bound on the "worst" algorithm time complexity.

Again consider the convex hull in $\mathbb{R}^d$, $d$ fixed, and ask: (a) Is the hull simplicial? or (b) Does the hull have exactly $F$ facets? Jeff Erickson showed (2) that, even for these decision questions, $\Omega( n \log n + n^{\lceil d/2 \rceil -1} )$ time is needed, matching the known upper bounds for odd $d$.

 

---

(1) Bernard Chazelle. "An optimal convex hull algorithm in any fixed dimension." Discrete & Computational Geometry, Volume 10 (1993), Number 4, 377–409. Zbl 0786.68091

(2) Jeff Erickson. "New Lower Bounds for Convex Hull Problems in Odd Dimensions." SIAM J. Comput., 28 (1999), 1198–1214. Zbl 0939.68047

 

---

An irrelevant aside: I coauthored an algorithm with time complexity $O(n^{42})$. :-)

I think the question needs to be sharpened to exclude algorithms that compute (or even involve) combinatorially complex structures. For example, the convex hull of $n$ points in $\mathbb{R}^d$ has size $\Theta(n^{\lfloor d/2 \rfloor})$ for fixed $d$. There is an asymptotically optimal algorithm (due to Chazelle (1)) to compute this hull in time $O( n \log n + n^{\lfloor d/2 \rfloor} )$. So one could exceed any power of $n$ in the time complexity by selection of a sufficiently large $d$.

So you need to specify that the algorithm is a decision procedure, outputting only one bit, Yes or No. But even here, there is no upper bound on the "worst" algorithm time complexity.

Again consider the convex hull in $\mathbb{R}^d$, $d$ fixed, and ask: (a) Is the hull simplicial? or (b) Does the hull have exactly $F$ facets? Jeff Erickson showed (2) that, even for these decision questions, $\Omega( n \log n + n^{\lceil d/2 \rceil -1} )$ time is needed, matching the known upper bounds for odd $d$.

---

(1) Bernard Chazelle. "[An optimal convex hull algorithm in any fixed dimension][1]." _Discrete & Computational Geometry_ Volume 10, Number 1, 377-409

(2) Jeff Erickson. "New Lower Bounds for Convex Hull Problems in Odd Dimensions." SIAM J. Comput., 28 (1995) 1-9.

I think the question needs to be sharpened to exclude algorithms that compute (or even involve) combinatorially complex structures. For example, the convex hull of $n$ points in $\mathbb{R}^d$ has size $\Theta(n^{\lfloor d/2 \rfloor})$ for fixed $d$. There is an asymptotically optimal algorithm (due to Chazelle (1)) to compute this hull in time $O( n \log n + n^{\lfloor d/2 \rfloor} )$. So one could exceed any power of $n$ in the time complexity by selection of a sufficiently large $d$.

So you need to specify that the algorithm is a decision procedure, outputting only one bit, Yes or No. But even here, there is no upper bound on the "worst" algorithm time complexity.

Again consider the convex hull in $\mathbb{R}^d$, $d$ fixed, and ask: (a) Is the hull simplicial? or (b) Does the hull have exactly $F$ facets? Jeff Erickson showed (2) that, even for these decision questions, $\Omega( n \log n + n^{\lceil d/2 \rceil -1} )$ time is needed, matching the known upper bounds for odd $d$.

---

(1) Bernard Chazelle. "[An optimal convex hull algorithm in any fixed dimension][1]." _Discrete & Computational Geometry_ Volume 10, Number 1, 377-409

(2) Jeff Erickson. "New Lower Bounds for Convex Hull Problems in Odd Dimensions." SIAM J. Comput., 28 (1995) 1-9.

---

An irrelevant aside: I coauthored an algorithm with time complexity $O(n^{42})$. :-)