0
$\begingroup$

Just trying to solve the second part of a question with two parts. First part was to prove that you can't add decrement method to a standart binary counter without hurting the amortized complexity and change it to be more than O(1). This part i have done with no problems.

Solution in a nutshell - after some method you are going to be in a dead end when you have a number like this: 100...0 so when you decrease by 1 you will get 0111...1 and then when you will increase by 1 you will get again 100...0 and those decreasment and increament are cost n and you will do them m times so its not O(1) amortized.

The second part, is to tell how you can change the structure such that it will support decreament and increase methods and the amortized complexity will stay O(1). I never saw something like this and it really confusing me what they want me to do. Their solution is that anytime you want to change 0 to 1 you change it to minus 1. Problem is, i can't understand what they meant, i mean, on which stracture you are inserting this change and how does it improved the complexity (if you change to -1 you stil going to the same dead end).

$\endgroup$
2
  • $\begingroup$ Aren't part one and part two contradicting each other? $\endgroup$
    – Nathaniel
    May 29 at 12:59
  • $\begingroup$ No because its a different stracture, but i am not sure i understand the question so that's why i am asking here so i am not sure $\endgroup$
    – yuval
    May 29 at 13:05
1
$\begingroup$

They may by suggesting that you use a binary counter with three digit values, $\{-1,0,1\}$, and budget a fixed additional time whenever you set a digit to $\pm1$.

To increment the counter you start at the least significant trit, and if it's $-1$ you set it to $0$ and stop, if it's $0$ you set it to $1$ and stop, and if it's $1$ you set it to $0$ and loop (using the previously budgeted time). Decrementing is the same with everything negated.

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