1
$\begingroup$

If an algorithm takes two numbers $b$ and $n$ and its input size satisfies $O(\log_2{n} + \log_2{b})$ plus its time complexity satisfies $O(b \log_{2}{n})$, what is the time complexity relative to the input size? Can we say it is exponential?

An algorithm is said to be exponential time, if $T(n)$ is upper bounded by $2^{poly(n)}$, where $poly(n)$ is some polynomial in $n$. More formally, an algorithm is exponential time if $T(n)$ is bounded by $O(2^{n^{k}})$ for some constant k.

Source

In that case, we can get the same input size with different combinations of $n$ and $b$, and by keeping $n$ fixed and changing $b$ the time grows much faster, so it's not directly possible to express time as a function of input size as it depends on what particular $b$ and $n$ constitute the input size.

By substituting $\log_{2}{b}$ with $b$ and $\log_2{n}$ with $n$, the input size is bounded by $O(b + n)$ and time by $O(2^b + n^2)$.

$\endgroup$

3 Answers 3

0
$\begingroup$

First of all, if all you're given is an upper bound on the input length, then you can't conclude anything. But I suspect that you meant that the input length is $\Theta(\log_2 n + \log_2 b)$. If there are no other constraints, then the best bound on the time complexity as a function of the input length $N$ is $O(2^N)$, since this is what happens when $n$ is constant.

$\endgroup$
2
  • $\begingroup$ Yes, obviously the upper bound will be $O(2^N)$ with fixed $n$, what I was focusing on was if there exists a name of algorithms whose time complexity upper bound relative to input size varies depending on how input of that particular size was constructed. In this case it can be either polynomial or exponential, but as we want to provide the smallest upper bound that covers all cases it's exponential as mentioned. $\endgroup$ Feb 19, 2022 at 21:25
  • 1
    $\begingroup$ You don't have to measure time complexity as a function of input length. The time complexity of many graph algorithms is measured as a function of the number of vertices and the number of edges, for example. $\endgroup$ Feb 19, 2022 at 21:57
0
$\begingroup$

Such an algorithm would run in pseudo-polynomial time.

$\endgroup$
0
$\begingroup$

With input size $O(n+m)$, the time complexity is $O(n2^b)$, which is linear in $n$ and exponential in $b$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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