Amortised Complexity

So far, algorithms and data structures we wrote have a fixed and isolated complexity. Sometimes, operations in isolation look expensive, but in groups are cheap. Datastructures often have invariances, that sometimes affect the complexities in odd ways. By default:

It would be nice to have a sequence where head, cons and tail have the same prroperties as last, snoc and init. We also want them to be fast:

data Deque a = Deque Int [a] [a]

Given the list xs = [1, 2, 3, 4, 5, 6], we have the following deques:

1. Deque 6 [1, 2, 3, 4, 5, 6] []
2. Deque 6 [1, 2, 3, 4, 5] [6]
3. Deque 6 [1, 2, 3, 4] [6, 5]
4. Deque 6 [1, 2, 3] [6, 5, 4]
5. Deque 6 [1, 2] [6, 5, 4, 3]
6. Deque 6 [1] [6, 5, 4, 3, 2]
7. Deque 6 [] [6, 5, 4, 3, 2, 1]

An invariance used is that xs = us ++ reverse sv.

1toList :: Deque a -> [a]
2toList (Deque _ us sv) = us ++ reverse sv
3
4nil :: Deque a
5nil = Deque 0 [] []
6
7cons :: a -> Deque a -> Deque a -- O(1)
8cons u (Deque n us sv) = Deque (n + 1) (u : us) sv
9
10snoc :: Deque a -> a -> Deque a -- O(1)
11snoc (Deque n us sv) v = Deque (n + 1) us (v : sv)
12
13fromList :: [a] -> Deque a
14fromList xs = Deque n us $ reverse vs
15    where n = Seq.length xs
16          (us, vs) = splitAd (div n 2) xs
17

This is not what we were looking for, as we were looking for somethat that is somewhat balanced, but totally balancing would be too much work.

1(==>) :: Bool -> Bool -> Bool
2False ==> _ = True
3True ==> x = x

We will add an invariance for minimally rebalancing (null sv ==> length us <= 1) && (null us ==> length sv <= 1). This is enough to give us a guaranteed constant time head and last:

1cons :: a -> Deque a -> Deque a
2cons u (Deque n sv []) = Deque (n + 1) [u] sv
3cons u (Deque n us sv) = Deque (n + 1) (u : us) sv
4
5snoc :: Deque a -> a -> Deque a
6snoc (Deque n [] us) v = Deque (n + 1) us [v]
7snoc (Deque n us sv) v = Deque (n + 1) us (v : sv)
8
9head :: Deque a -> a
10head (Deque _ [] [v]) = v -- O(1)
11head (Deque _ (u : _) _) = u -- O(1)
12
13last :: Deque a -> a
14last (Deque _ [u] []) = u -- O(1)
15last (Deque _ _ (v : _)) = v -- O(1)

Symmetrical and fast. Now, head, last, cons and snoc all have . Now, lets implement tail and init:

1tail :: Deque a -> Deque a
2tail (Deque 0 _ _) = undefined  -- O(1)
3tail (Deque 1 _ _) = nil -- O(1)
4tail (Deque _ [_] sv) = fromList $ reverse sv -- O(n)
5tail (Deque n (_ : us) sv) = Deque (n - 1) us sv -- O(1)
6
7init :: Deque a -> Deque a
8init (Deque 0 _ _) = undefined -- O(1)
9init (Deque 1 _ _) = nil -- O(1)
10init (Deque _ us [_]) = fromList us -- O(n)
11init (Deque n us (_ : sv)) = Deque (n - 1) us sv -- O(1)

Although symmetric, it appears the functions init and tail are expensive as , In reality, this is NOT the case. Looking at this example for 16 tails:

1[ Deque 16 [1] [16,15,14,13,12,11,10,9,8,7,6,5,4,3,2] -- O(n)
2, Deque 15 [2,3,4,5,6,7,8] [16,15,14,13,12,11,10,9]   -- O(1)
3, Deque 14 [3,4,5,6,7,8] [16,15,14,13,12,11,10,9],    -- O(1)
4, Deque 13 [4,5,6,7,8] [16,15,14,13,12,11,10,9],      -- O(1)
5, Deque 12 [5,6,7,8] [16,15,14,13,12,11,10,9],        -- O(1)
6, Deque 11 [6,7,8] [16,15,14,13,12,11,10,9],          -- O(1)
7, Deque 10 [7,8] [16,15,14,13,12,11,10,9],            -- O(1)
8, Deque 9 [8] [16,15,14,13,12,11,10,9],               -- O(n/2)
9, Deque 8 [9,10,11,12] [16,15,14,13]                  -- O(1)
10, Deque 7 [10,11,12] [16,15,14,13]                    -- O(1)
11, Deque 6 [11,12] [16,15,14,13],                      -- O(1)
12, Deque 5 [12] [16,15,14,13],                         -- O(n/4)
13, Deque 4 [13,14] [16,15],                            -- O(1)
14, Deque 3 [14] [16,15],                               -- O(n/8)
15, Deque 2 [15] [16],                                  -- O(1)
16, Deque 1 [] [16],                                    -- O(1)
17, Deque 0 [] []
18]

If you sum these you'll get n + n / 2 + n / 4 + n / 8... = 2n and then a bunch of s, for a total cost of for tails. This is an amortised cost of per tail. This is the power of amortised complexity.

Amortised complexity is like a piggy-bank. We overpay and save every time we do something cheap, so that we have pocket money to pay for nice expensive tails.

Amortised analysis needs three things:

• A cost function that gives the cost of operation on state .
• An amortised cost function that gives the amortised cost of operation on state .
• A potential function which gives a measure of how close the next expensive operation will be.

These functions form a relationship:

If this relationship is true, the operation has complexity .

The function allows us to record the fact that sometimes overpays. You cannot simplify pick any function: it must be at its largest just before something expensive, and at its smallest just after something expensive. Let's consider the tail example:

1C_tail (Deque 1 _ _)     = 1
2C_tail (Deque _ [_] _)   = n - 1
3C_tail (Deque _ (_:_) _) = 1

We will assume that the amortised cost of tail is a constant :

A_tail xs = k

Due to the nature of the problem, we want to be when the deque is balanced, and when it is maximally unbalanced. We will use the following potential function:

Phi (Deque n us sv) = max (length us - length sv) 0

When length us == 1, we are about to hit the expensive case next, so length sv == n - 1 and the potential is n - 2. When length us == n / 2, we are about to hit the cheap case next, so length sv == n / 2 and the potential is 0. This is the right potential function for this problem.

Now, we can prove that the relationship holds for all cases of C_tail:

worst case, we end up with 0 as the potential of the singleton deque.

Now, if us is longer than sv, then . If sv is longer than us, then let and :

Finally, with the last case:

Hence, for all cases we can see that the actual complexity of tail is , which is constant time, or .