974:
1528:
Therefore, with this choice of resizing strategy and potential function, the potential method shows that all dynamic array operations take constant amortized time. Combining this with the inequality relating amortized time and actual time over sequences of operations, this shows that any sequence of
292:
680:
1505:
When an increase-size operation does not lead to a resize operation, Φ increases by 2, a constant. Therefore, the constant actual time of the operation and the constant increase in potential combine to give a constant amortized time for an operation of this type.
1144:
1540:
When the dynamic array includes operations that decrease the array size as well as increasing it, the potential function must be modified to prevent it from becoming negative. One way to do this is to replace the formula above for Φ by its
544:
669:
1524:
The other operations of the data structure (reading and writing array cells without changing the array size) do not cause the potential function to change and have the same constant amortized time as their actual time.
1334:, so the amortized time can be used to provide an accurate upper bound on the actual time of a sequence of operations, even though the amortized time for an individual operation may vary widely from its actual time.
1332:
1703:. Then, if the LSB were flipped from 1 to 0, then the next bit is also flipped. This goes on until finally a bit is flipped from 0 to 1, at which point the flipping stops. If the counter initially ends in
106:
1383:
With this definition, the time to perform a sequence of operations may be estimated by multiplying the amortized time for each type of operation in the sequence by the number of operations of that type.
301:
is a non-negative constant of proportionality (in units of time) that must remain fixed throughout the analysis. That is, the amortized time is defined to be the actual time taken by the operation plus
1436:
representing the positions within the array that have been used so far. With this structure, random accesses to the dynamic array may be implemented by accessing the same cell of the internal array
969:{\displaystyle T_{\mathrm {amortized} }(O)=\sum _{i=1}^{n}\left(T_{\mathrm {actual} }(o_{i})+C\cdot (\Phi (S_{i})-\Phi (S_{i-1}))\right)=T_{\mathrm {actual} }(O)+C\cdot (\Phi (S_{n})-\Phi (S_{0})),}
399:
1231:
989:
1189:
1354:
is an integer defining the size of the given data structure (for instance, the number of items that it contains), then the amortized time for operations of type
408:
551:
1509:
However, when an increase-size operation causes a resize, the potential value of Φ decreases to zero after the resize. Allocating a new internal array
1743:
in which removing an item takes logarithmic amortized time, and all other operations take constant amortized time. It may also be used to analyze
1236:
59:
stored in that state. The potential value prior to the operation of initializing a data structure is defined to be zero. Alternatively, Φ(
1521:) this is entirely cancelled by the decrease in the potential function, leaving again a constant total amortized time for the operation.
1846:
Goodrich and
Tamassia, 1.5.2 Analyzing an Extendable Array Implementation, pp. 139–141; Cormen et al., 17.4 Dynamic tables, pp. 416–424.
310:
287:{\displaystyle T_{\mathrm {amortized} }(o)=T_{\mathrm {actual} }(o)+C\cdot (\Phi (S_{\mathrm {after} })-\Phi (S_{\mathrm {before} })),}
1537:) actual time in the worst case, despite the fact that some of the individual operations may themselves take a linear amount of time.
1831:
1673:, but instead require one unit of time per bit operation in the increment. We wish to show that Inc takes O(1) amortized time.
1880:
20:
35:, a measure of its performance over sequences of operations that smooths out the cost of infrequent but expensive operations.
1670:
983:
in which all terms other than the initial and final potential function values cancel in pairs. Rearranging this, we obtain:
1414:
1410:
51:) represents work that has been accounted for ("paid for") in the amortized analysis but not yet performed. Thus, Φ(
1821:
1554:
43:
In the potential method, a function Φ is chosen that maps states of the data structure to non-negative numbers. If
339:
329:
Despite its artificial appearance, the total amortized time of a sequence of operations provides a valid
1700:
1194:
1139:{\displaystyle T_{\mathrm {actual} }(O)=T_{\mathrm {amortized} }(O)-C\cdot (\Phi (S_{n})-\Phi (S_{0})).}
1809:
1402:
1409:
to positions within the array and the ability to increase the array size by one. It is available in
1358:
is defined to be the maximum, among all possible sequences of operations on data structures of size
1152:
1773:
1448:
an operation that increases the dynamic array size may be implemented simply by incrementing
1748:
980:
28:
1827:
1644:
1613:
A Push operation takes constant time and increases Φ by 1, so its amortized time is constant.
1805:
1777:
56:
539:{\displaystyle T_{\mathrm {amortized} }(O)=\sum _{i=1}^{n}T_{\mathrm {amortized} }(o_{i}),}
74:
be any individual operation within a sequence of operations on some data structure, with
1817:
1740:
1736:
1685:
1542:
314:
32:
1502:
to be at least half-full, this potential function is always non-negative, as desired.
1874:
1648:
1406:
1398:
664:{\displaystyle T_{\mathrm {actual} }(O)=\sum _{i=1}^{n}T_{\mathrm {actual} }(o_{i}).}
1517:) actual time, but (with an appropriate choice of the constant of proportionality
1513:
and copying all of the values from the old internal array to the new one takes O(
330:
1813:
1744:
1420:
A dynamic array may be implemented by a data structure consisting of an array
1343:
96:
has completed. Once Φ has been chosen, the amortized time for operation
1591:) time, but we wish to show that all operations take O(1) amortized time.
1564:
Push - add a single element on top of the stack, enlarging the stack by 1.
1350:
is a type of operation that may be performed by the data structure, and
1327:{\displaystyle T_{\mathrm {actual} }(O)\leq T_{\mathrm {amortized} }(O)}
1464:, and a common strategy for doing so is to double its size, replacing
1719:−1, so the amortized time is 2. Hence, the actual time for running
63:) may be thought of as representing the amount of disorder in state
1696:
This number is always non-negative and starts with 0, as required.
16:
Method of analyzing the amortized complexity of a data structure
1864:
Goodrich and
Tamassia, Section 3.4, "Splay Trees", pp. 185–194.
1346:
assumption about the input sequence. With this assumption, if
1826:(2nd ed.). MIT Press and McGraw-Hill. pp. 412–416.
1782:
Algorithm Design: Foundations, Analysis and
Internet Examples
1676:
This structure may be analyzed using the potential function:
1594:
This structure may be analyzed using the potential function:
1475:
This structure may be analyzed using the potential function:
1342:
Typically, amortized analysis is used in combination with a
81:
denoting the state of the data structure prior to operation
306:
times the difference in potential caused by the operation.
1855:
Cormen et al., Chapter 20, "Fibonacci Heaps", pp. 476–497.
1735:
The potential function method is commonly used to analyze
1373:
within the sequence, of the amortized time for operation
979:
where the sequence of potential function values forms a
333:
on the actual time for the same sequence of operations.
317:, constant factors are irrelevant and so the constant
1239:
1197:
1155:
992:
683:
554:
411:
342:
109:
1326:
1225:
1183:
1138:
968:
663:
538:
393:
286:
1610:This number is always non-negative, as required.
55:) may be thought of as calculating the amount of
1751:with logarithmic amortized time per operation.
8:
1684:Φ = number-of-bits-equal-to-1 =
1655:Initialize: create a counter with value 0.
1624:, so its amortized time is also constant.
1575:elements from the top of the stack, where
1498:Since the resizing strategy always causes
394:{\displaystyle O=o_{1},o_{2},\dots ,o_{n}}
325:Relation between amortized and actual time
1780:(2002), "1.5.1 Amortization Techniques",
1651:and supporting the following operations:
1602:Φ = number-of-elements-in-stack
1557:which supports the following operations:
1284:
1283:
1245:
1244:
1238:
1208:
1196:
1166:
1154:
1121:
1099:
1037:
1036:
998:
997:
991:
951:
929:
876:
875:
845:
823:
792:
763:
762:
747:
736:
689:
688:
682:
649:
620:
619:
609:
598:
560:
559:
553:
524:
486:
485:
475:
464:
417:
416:
410:
385:
366:
353:
341:
253:
252:
217:
216:
163:
162:
115:
114:
108:
1768:
1766:
1764:
1760:
1661:Read: return the current counter value.
1401:is a data structure for maintaining an
1338:Amortized analysis of worst-case inputs
1820:(2001) . "17.3 The potential method".
1800:
1798:
1796:
1794:
1792:
1579:is no more than the current stack size
67:or its distance from an ideal state.
7:
47:is a state of the data structure, Φ(
1561:Initialize - create an empty stack.
311:asymptotic computational complexity
92:denoting its state after operation
29:amortized time and space complexity
1309:
1306:
1303:
1300:
1297:
1294:
1291:
1288:
1285:
1261:
1258:
1255:
1252:
1249:
1246:
1226:{\displaystyle \Phi (S_{n})\geq 0}
1198:
1156:
1111:
1089:
1062:
1059:
1056:
1053:
1050:
1047:
1044:
1041:
1038:
1014:
1011:
1008:
1005:
1002:
999:
941:
919:
892:
889:
886:
883:
880:
877:
835:
813:
779:
776:
773:
770:
767:
764:
714:
711:
708:
705:
702:
699:
696:
693:
690:
636:
633:
630:
627:
624:
621:
576:
573:
570:
567:
564:
561:
511:
508:
505:
502:
499:
496:
493:
490:
487:
442:
439:
436:
433:
430:
427:
424:
421:
418:
269:
266:
263:
260:
257:
254:
242:
230:
227:
224:
221:
218:
206:
179:
176:
173:
170:
167:
164:
140:
137:
134:
131:
128:
125:
122:
119:
116:
14:
1715:+1 and reducing the potential by
1635:) actual time in the worst case.
1627:This proves that any sequence of
1533:dynamic array operations takes O(
27:is a method used to analyze the
1468:by a new array of length 2
1413:as the "ArrayList" type and in
336:For any sequence of operations
21:computational complexity theory
1671:transdichotomous machine model
1321:
1315:
1273:
1267:
1214:
1201:
1184:{\displaystyle \Phi (S_{0})=0}
1172:
1159:
1130:
1127:
1114:
1105:
1092:
1086:
1074:
1068:
1026:
1020:
960:
957:
944:
935:
922:
916:
904:
898:
860:
857:
838:
829:
816:
810:
798:
785:
726:
720:
655:
642:
588:
582:
530:
517:
454:
448:
278:
275:
245:
236:
209:
203:
191:
185:
152:
146:
1:
1616:A Pop operation takes time O(
1711:+1 bits, taking actual time
1460:, it is necessary to resize
39:Definition of amortized time
1747:, a self-adjusting form of
1707:1 bits, we flip a total of
1699:An Inc operation flips the
1897:
1823:Introduction to Algorithms
1658:Inc: add 1 to the counter.
405:The total amortized time:
1665:For this example, we are
1428:, together with a number
1424:of items, of some length
1620:) but also reduces Φ by
1405:of items, allowing both
1784:, Wiley, pp. 36–38
548:The total actual time:
1881:Analysis of algorithms
1328:
1227:
1185:
1140:
970:
752:
665:
614:
540:
480:
395:
288:
1810:Leiserson, Charles E.
1701:least significant bit
1329:
1228:
1186:
1141:
971:
732:
666:
594:
541:
460:
396:
289:
1774:Goodrich, Michael T.
1723:Inc operations is O(
1417:as the "list" type.
1237:
1195:
1153:
990:
681:
552:
409:
340:
321:is usually omitted.
107:
1631:operations takes O(
1487: −
1362:and all operations
1749:binary search tree
1324:
1223:
1181:
1136:
981:telescoping series
966:
661:
536:
391:
284:
1814:Rivest, Ronald L.
1806:Cormen, Thomas H.
1778:Tamassia, Roberto
1647:represented as a
100:is defined to be
1888:
1865:
1862:
1856:
1853:
1847:
1844:
1838:
1837:
1802:
1787:
1785:
1770:
1452:. However, when
1444: <
1333:
1331:
1330:
1325:
1314:
1313:
1312:
1266:
1265:
1264:
1232:
1230:
1229:
1224:
1213:
1212:
1190:
1188:
1187:
1182:
1171:
1170:
1145:
1143:
1142:
1137:
1126:
1125:
1104:
1103:
1067:
1066:
1065:
1019:
1018:
1017:
975:
973:
972:
967:
956:
955:
934:
933:
897:
896:
895:
867:
863:
856:
855:
828:
827:
797:
796:
784:
783:
782:
751:
746:
719:
718:
717:
670:
668:
667:
662:
654:
653:
641:
640:
639:
613:
608:
581:
580:
579:
545:
543:
542:
537:
529:
528:
516:
515:
514:
479:
474:
447:
446:
445:
400:
398:
397:
392:
390:
389:
371:
370:
358:
357:
293:
291:
290:
285:
274:
273:
272:
235:
234:
233:
184:
183:
182:
145:
144:
143:
57:potential energy
25:potential method
1896:
1895:
1891:
1890:
1889:
1887:
1886:
1885:
1871:
1870:
1869:
1868:
1863:
1859:
1854:
1850:
1845:
1841:
1834:
1818:Stein, Clifford
1804:
1803:
1790:
1772:
1771:
1762:
1757:
1737:Fibonacci heaps
1733:
1641:
1551:
1549:Multi-Pop Stack
1483:Φ = 2
1395:
1390:
1378:
1367:
1340:
1279:
1240:
1235:
1234:
1204:
1193:
1192:
1162:
1151:
1150:
1117:
1095:
1032:
993:
988:
987:
947:
925:
871:
841:
819:
788:
758:
757:
753:
684:
679:
678:
645:
615:
555:
550:
549:
520:
481:
412:
407:
406:
381:
362:
349:
338:
337:
327:
248:
212:
158:
110:
105:
104:
91:
80:
41:
17:
12:
11:
5:
1894:
1892:
1884:
1883:
1873:
1872:
1867:
1866:
1857:
1848:
1839:
1832:
1788:
1759:
1758:
1756:
1753:
1741:priority queue
1732:
1729:
1694:
1693:
1692:
1691:
1690:
1689:
1663:
1662:
1659:
1656:
1640:
1639:Binary counter
1637:
1608:
1607:
1606:
1605:
1604:
1603:
1581:
1580:
1565:
1562:
1550:
1547:
1543:absolute value
1496:
1495:
1494:
1493:
1492:
1491:
1394:
1391:
1389:
1386:
1376:
1365:
1339:
1336:
1323:
1320:
1317:
1311:
1308:
1305:
1302:
1299:
1296:
1293:
1290:
1287:
1282:
1278:
1275:
1272:
1269:
1263:
1260:
1257:
1254:
1251:
1248:
1243:
1222:
1219:
1216:
1211:
1207:
1203:
1200:
1180:
1177:
1174:
1169:
1165:
1161:
1158:
1147:
1146:
1135:
1132:
1129:
1124:
1120:
1116:
1113:
1110:
1107:
1102:
1098:
1094:
1091:
1088:
1085:
1082:
1079:
1076:
1073:
1070:
1064:
1061:
1058:
1055:
1052:
1049:
1046:
1043:
1040:
1035:
1031:
1028:
1025:
1022:
1016:
1013:
1010:
1007:
1004:
1001:
996:
977:
976:
965:
962:
959:
954:
950:
946:
943:
940:
937:
932:
928:
924:
921:
918:
915:
912:
909:
906:
903:
900:
894:
891:
888:
885:
882:
879:
874:
870:
866:
862:
859:
854:
851:
848:
844:
840:
837:
834:
831:
826:
822:
818:
815:
812:
809:
806:
803:
800:
795:
791:
787:
781:
778:
775:
772:
769:
766:
761:
756:
750:
745:
742:
739:
735:
731:
728:
725:
722:
716:
713:
710:
707:
704:
701:
698:
695:
692:
687:
672:
671:
660:
657:
652:
648:
644:
638:
635:
632:
629:
626:
623:
618:
612:
607:
604:
601:
597:
593:
590:
587:
584:
578:
575:
572:
569:
566:
563:
558:
546:
535:
532:
527:
523:
519:
513:
510:
507:
504:
501:
498:
495:
492:
489:
484:
478:
473:
470:
467:
463:
459:
456:
453:
450:
444:
441:
438:
435:
432:
429:
426:
423:
420:
415:
388:
384:
380:
377:
374:
369:
365:
361:
356:
352:
348:
345:
326:
323:
315:big O notation
309:When studying
295:
294:
283:
280:
277:
271:
268:
265:
262:
259:
256:
251:
247:
244:
241:
238:
232:
229:
226:
223:
220:
215:
211:
208:
205:
202:
199:
196:
193:
190:
187:
181:
178:
175:
172:
169:
166:
161:
157:
154:
151:
148:
142:
139:
136:
133:
130:
127:
124:
121:
118:
113:
89:
78:
40:
37:
33:data structure
15:
13:
10:
9:
6:
4:
3:
2:
1893:
1882:
1879:
1878:
1876:
1861:
1858:
1852:
1849:
1843:
1840:
1835:
1833:0-262-03293-7
1829:
1825:
1824:
1819:
1815:
1811:
1807:
1801:
1799:
1797:
1795:
1793:
1789:
1783:
1779:
1775:
1769:
1767:
1765:
1761:
1754:
1752:
1750:
1746:
1742:
1738:
1730:
1728:
1726:
1722:
1718:
1714:
1710:
1706:
1702:
1697:
1687:
1686:hammingweight
1683:
1682:
1681:
1680:
1679:
1678:
1677:
1674:
1672:
1668:
1660:
1657:
1654:
1653:
1652:
1650:
1649:binary number
1646:
1638:
1636:
1634:
1630:
1625:
1623:
1619:
1614:
1611:
1601:
1600:
1599:
1598:
1597:
1596:
1595:
1592:
1590:
1587:) requires O(
1586:
1578:
1574:
1570:
1566:
1563:
1560:
1559:
1558:
1556:
1548:
1546:
1544:
1538:
1536:
1532:
1526:
1522:
1520:
1516:
1512:
1507:
1503:
1501:
1490:
1486:
1482:
1481:
1480:
1479:
1478:
1477:
1476:
1473:
1471:
1467:
1463:
1459:
1456: =
1455:
1451:
1447:
1443:
1439:
1435:
1432: ≤
1431:
1427:
1423:
1418:
1416:
1412:
1408:
1407:random access
1404:
1400:
1399:dynamic array
1393:Dynamic array
1392:
1387:
1385:
1381:
1379:
1372:
1368:
1361:
1357:
1353:
1349:
1345:
1337:
1335:
1318:
1280:
1276:
1270:
1241:
1220:
1217:
1209:
1205:
1178:
1175:
1167:
1163:
1133:
1122:
1118:
1108:
1100:
1096:
1083:
1080:
1077:
1071:
1033:
1029:
1023:
994:
986:
985:
984:
982:
963:
952:
948:
938:
930:
926:
913:
910:
907:
901:
872:
868:
864:
852:
849:
846:
842:
832:
824:
820:
807:
804:
801:
793:
789:
759:
754:
748:
743:
740:
737:
733:
729:
723:
685:
677:
676:
675:
658:
650:
646:
616:
610:
605:
602:
599:
595:
591:
585:
556:
547:
533:
525:
521:
482:
476:
471:
468:
465:
461:
457:
451:
413:
404:
403:
402:
386:
382:
378:
375:
372:
367:
363:
359:
354:
350:
346:
343:
334:
332:
324:
322:
320:
316:
312:
307:
305:
300:
281:
249:
239:
213:
200:
197:
194:
188:
159:
155:
149:
111:
103:
102:
101:
99:
95:
88:
84:
77:
73:
68:
66:
62:
58:
54:
50:
46:
38:
36:
34:
30:
26:
22:
1860:
1851:
1842:
1822:
1781:
1739:, a form of
1734:
1731:Applications
1724:
1720:
1716:
1712:
1708:
1704:
1698:
1695:
1675:
1666:
1664:
1642:
1632:
1628:
1626:
1621:
1617:
1615:
1612:
1609:
1593:
1588:
1584:
1582:
1576:
1572:
1568:
1552:
1539:
1534:
1530:
1527:
1523:
1518:
1514:
1510:
1508:
1504:
1499:
1497:
1488:
1484:
1474:
1469:
1465:
1461:
1457:
1453:
1449:
1445:
1441:
1437:
1433:
1429:
1425:
1421:
1419:
1396:
1382:
1374:
1370:
1363:
1359:
1355:
1351:
1347:
1341:
1148:
978:
673:
335:
328:
318:
308:
303:
298:
296:
97:
93:
86:
82:
75:
71:
69:
64:
60:
52:
48:
44:
42:
24:
18:
1745:splay trees
1643:Consider a
1571:) - remove
1553:Consider a
1440:, and when
331:upper bound
1755:References
1669:using the
1344:worst case
401:, define:
1688:(counter)
1277:≤
1218:≥
1199:Φ
1157:Φ
1112:Φ
1109:−
1090:Φ
1084:⋅
1078:−
942:Φ
939:−
920:Φ
914:⋅
850:−
836:Φ
833:−
814:Φ
808:⋅
734:∑
596:∑
462:∑
376:…
243:Φ
240:−
207:Φ
201:⋅
1875:Category
1388:Examples
1369:of type
1645:counter
1830:
1415:Python
1149:Since
674:Then:
313:using
297:where
79:before
23:, the
1555:stack
1403:array
90:after
31:of a
1828:ISBN
1583:Pop(
1567:Pop(
1411:Java
1191:and
85:and
70:Let
1727:).
1667:not
19:In
1877::
1816:;
1812:;
1808:;
1791:^
1776:;
1763:^
1545:.
1472:.
1397:A
1380:.
1233:,
1836:.
1786:.
1725:m
1721:m
1717:k
1713:k
1709:k
1705:k
1633:m
1629:m
1622:k
1618:k
1589:k
1585:k
1577:k
1573:k
1569:k
1535:n
1531:n
1519:C
1515:n
1511:A
1500:A
1489:N
1485:n
1470:n
1466:A
1462:A
1458:N
1454:n
1450:n
1446:N
1442:n
1438:A
1434:N
1430:n
1426:N
1422:A
1377:i
1375:o
1371:X
1366:i
1364:o
1360:n
1356:X
1352:n
1348:X
1322:)
1319:O
1316:(
1310:d
1307:e
1304:z
1301:i
1298:t
1295:r
1292:o
1289:m
1286:a
1281:T
1274:)
1271:O
1268:(
1262:l
1259:a
1256:u
1253:t
1250:c
1247:a
1242:T
1221:0
1215:)
1210:n
1206:S
1202:(
1179:0
1176:=
1173:)
1168:0
1164:S
1160:(
1134:.
1131:)
1128:)
1123:0
1119:S
1115:(
1106:)
1101:n
1097:S
1093:(
1087:(
1081:C
1075:)
1072:O
1069:(
1063:d
1060:e
1057:z
1054:i
1051:t
1048:r
1045:o
1042:m
1039:a
1034:T
1030:=
1027:)
1024:O
1021:(
1015:l
1012:a
1009:u
1006:t
1003:c
1000:a
995:T
964:,
961:)
958:)
953:0
949:S
945:(
936:)
931:n
927:S
923:(
917:(
911:C
908:+
905:)
902:O
899:(
893:l
890:a
887:u
884:t
881:c
878:a
873:T
869:=
865:)
861:)
858:)
853:1
847:i
843:S
839:(
830:)
825:i
821:S
817:(
811:(
805:C
802:+
799:)
794:i
790:o
786:(
780:l
777:a
774:u
771:t
768:c
765:a
760:T
755:(
749:n
744:1
741:=
738:i
730:=
727:)
724:O
721:(
715:d
712:e
709:z
706:i
703:t
700:r
697:o
694:m
691:a
686:T
659:.
656:)
651:i
647:o
643:(
637:l
634:a
631:u
628:t
625:c
622:a
617:T
611:n
606:1
603:=
600:i
592:=
589:)
586:O
583:(
577:l
574:a
571:u
568:t
565:c
562:a
557:T
534:,
531:)
526:i
522:o
518:(
512:d
509:e
506:z
503:i
500:t
497:r
494:o
491:m
488:a
483:T
477:n
472:1
469:=
466:i
458:=
455:)
452:O
449:(
443:d
440:e
437:z
434:i
431:t
428:r
425:o
422:m
419:a
414:T
387:n
383:o
379:,
373:,
368:2
364:o
360:,
355:1
351:o
347:=
344:O
319:C
304:C
299:C
282:,
279:)
276:)
270:e
267:r
264:o
261:f
258:e
255:b
250:S
246:(
237:)
231:r
228:e
225:t
222:f
219:a
214:S
210:(
204:(
198:C
195:+
192:)
189:o
186:(
180:l
177:a
174:u
171:t
168:c
165:a
160:T
156:=
153:)
150:o
147:(
141:d
138:e
135:z
132:i
129:t
126:r
123:o
120:m
117:a
112:T
98:o
94:o
87:S
83:o
76:S
72:o
65:S
61:S
53:S
49:S
45:S
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.