# Can an algorithm complexity be lower than its tight low bound / higher than its tight high bound?

The worst case time complexity of a given algorithm is $$\theta(n^3logn)$$.
Is it possible that the worst time complexity is $$\Omega(n^2)$$?
Is it possible that the worst time complexity is $$O(n^4)$$?
The average time complexity is $$O(n^4)$$?

IMO it is possible as long as you control the constant $$c$$, but then what's the point of mentioning any other bound than the tight bounds?

## 3 Answers

Let $$t(x)$$ be the time taken for input $$x\in \{0,1\}^*$$, and $$T(n)=\max_{x\in\{0,1\}^*,|x|=n}t(x)$$ is the worst case.

If $$T\in\theta(n^3\log(n))$$, this means that there are constants $$C_1,C_2$$ and $$N$$ such that for all $$n> N$$ you have $$C_1n^3\log(n)\leq T(n)\leq C_2n^3\log(n)$$.

Since $$n^3\log(n)\geq n^2$$ for $$n>1$$, then $$C_1n^2\leq C_1n^3\log(n)\leq T(n)$$. Therefore, $$T\in\Omega(n^2)$$.

We also have that $$n^3\log(n)\leq n^4$$, for all $$n>1$$. Therefore, $$T(n)\leq C_2n^3\log(n)\leq C_2n^4$$.

This implies that $$T\in O(n^4)$$.

Finally, \begin{align}A(n)&=E(t(x), |x|=n)\\&\leq E(T(n), |x|=n)\\&=T(n)E(1,|x|=n)\\&=T(n)\\&\leq C_2n^3\log(n)\\&\leq C_2n^4\end{align}, for $$n>1$$. Therefore, the average number of steps satisfies $$A\in O(n^4)$$.

Sometimes computing tight bounds is hard, while more relaxed bounds are more accessible.

If $$T(n) = \Theta(n^3\log n)$$ then it is always the case that $$T(n) = \Omega(n^2)$$ and $$T(n) = O(n^4)$$.

If $$T(n)$$ is the worst-case complexity of an algorithm, then furthermore its average-case complexity is $$O(n^4)$$, always.

Sometimes the algorithm you have or the recurrence relation you have do not give you enough information other than the upper bounded relation. i.e. $$T(n) \le 2T(n/2) + n$$. So you can only upper bound the algorithm unless you have additional information on the lower bound as well.