What time complexity relative to input size is that?

Question

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)$.

Answer 1

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.

Answer 2

Such an algorithm would run in pseudo-polynomial time.

Answer 3

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