0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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