next up previous
Next: 4.6.5 Amortized Analysis of Splaying Up: 4.6 Amortized Algorithm Analysis Previous: 4.6.3 Credit Balance

4.6.4 Example of Incrementing Binary Integers

Step i Integer tiCiai

0 --- 0000 ---- - 0 -

1 --- 0001 ---- 1 1 2

2 --- 0010 ---- 2 1 2

3 --- 0011 ---- 1 2 2

4 --- 0100 ---- 3 1. 2

5 --- 0101 ---- 1 2 2

6 --- 0110 ---- 2 2 2

7 --- 0111 ---- 1 3 2

8 --- 1000 ---- 4 1 2

9 --- 1001 ---- 1 2 2

10 --- 1010 ---- 2 2 2

11 --- 1011 ---- 1 3 2

12 --- 1100 ---- 3 2 2

13 --- 1101 ---- 1 3 2

14 --- 1110 ---- 2 3 2

15 --- 1111 ---- 1 4 2

16 --- 0000 ---- 4 0 0


next up previous
Next: 4.6.5 Amortized Analysis of Splaying Up: 4.6 Amortized Algorithm Analysis Previous: 4.6.3 Credit Balance
eEL,CSA_Dept,IISc,Bangalore