# What time complexity relative to input size is that?

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

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.
• 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. Feb 19, 2022 at 21:25
With input size $$O(n+m)$$, the time complexity is $$O(n2^b)$$, which is linear in $$n$$ and exponential in $$b$$.