I have a problem with expressing binary length of ternary sequence. One of the questions at tutorial sheet from algorithmics specified a question, which can be simplified to a below problem:

We have a polynomial $P(n)$, which tells the running time complexity of some algorithm (where $n$ is the binary length of the sequence we are passing as an argument). The goal is to find polynomial $P_{1}(k)$, where $k$ is the ternary lengh of some ternary sequence.

So, to find $P_{1}(k)$ I need to find a relationship between $n$ and $k$. I know that if we have number $x$, then its' binary length $n$ follows the relationship: $$n=\left \lfloor{\mathrm{log}_{2}(x)}\right \rfloor +1$$ From the same equation we can express ternary length of the number $x$: $$k=\left \lfloor{\mathrm{log}_{3}(x)}\right \rfloor +1$$
So, we could use those two to create a realation between $n$ and $k$, but I have no idea how to safely act arround floor functions. Is there any way to nicely solve it? If not, is there any way to escape floor functions and get upper and lower bounds I could use to estimate the final complexity?

I would be most grateful for your help!


Your Answer

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

Browse other questions tagged or ask your own question.