amortized complexity - 2024 ACF Regionals

Question

The banker’s and physicist’s methods are the most common ways of analyzing this quantity. For 10 points each:

[10m] Name this measure of average computational complexity that is less pessimistic than worse-case complexity, since it accounts for cases where the worst case happens infrequently.

ANSWER: amortized complexity [accept amortized runtime]

[10h] Amortized analysis assumes that each operation’s output is an input to the next one, making it apt for this class of algorithms similar to streaming algorithms. These algorithms do not see the whole input at once, but instead must act each time they see a piece.

ANSWER: online algorithms

[10e] A variant of this data structure that dynamically resizes has a constant amortized runtime for insertion. This one-dimensional data structure has fixed capacity and its contents can be accessed by index.

ANSWER: array [accept array list; prompt on list]

Back to bonuses

Summary


2024 ACF Regionals @ Berkeley	01/27/2024	Y	3	13.33	67%	0%	67%
2024 ACF Regionals @ Cornell	01/27/2024	Y	3	13.33	100%	0%	33%
2024 ACF Regionals @ JMU	01/27/2024	Y	9	12.22	89%	22%	11%
2024 ACF Regionals @ Minnesota	01/27/2024	Y	2	15.00	100%	50%	0%
2024 ACF Regionals @ Ohio State	01/27/2024	Y	3	6.67	67%	0%	0%
2024 ACF Regionals @ Rutgers	01/27/2024	Y	5	10.00	60%	20%	20%
2024 ACF Regionals @ Imperial	01/27/2024	Y	8	12.50	88%	25%	13%
2024 ACF Regionals @ Vanderbilt	01/27/2024	Y	5	6.00	60%	0%	0%
2024 ACF Regionals @ MIT	01/27/2024	Y	3	3.33	33%	0%	0%

Data


Berkeley C	Stanford B	0	0	0	0
Stanford A	Stanford C	0	10	10	20
Oxford C	Cambridge A	10	0	10	20
Edinburgh	Cambridge C	0	0	10	10
Geodesic	Georgia Tech B	0	0	10	10
Vanderbilt A	Harding	0	0	10	10
Berkeley A	Berkeley B	0	10	10	20
Cornell A	Binghamton	0	10	10	20
Cornell C	Cornell B	0	0	10	10
RIT A	RIT B	0	0	10	10
GWU A (UG)	UNC D (DII)	10	0	10	20
William & Mary A (UG)	GWU B (Grad)	0	0	0	0
Maryland A (Grad)	Liberty C (DII)	10	0	10	20
Kenyon	Cedarville	0	0	10	10
Columbia A	NYU B	0	10	10	20
Bristol	Imperial A	0	0	0	0
Oxford B	Imperial B	0	0	10	10
Oxford A	KCL	10	10	10	30
Cambridge B	Kiel	0	0	10	10
Durham A	Sheffield	0	0	10	10
Warwick	Durham B	0	0	10	10
MTSU	Alabama	0	0	0	0
Tennessee	South Carolina	0	0	0	0
Vanderbilt B	Georgia Tech A	0	0	10	10
Dartmouth A	Brandeis B	0	0	0	0
Yale A	Harvard B	0	0	0	0
Virginia B (UG)	Duke A (UG)	0	0	10	10
Virginia C (UG)	JMU A (UG)	0	0	10	10
Maryland C (DII)	Liberty A (Grad)	0	0	10	10
Liberty B (DII)	Virginia A (UG)	0	0	10	10
Maryland B (UG)	Roanoke College A (DII)	0	0	10	10
UNC B (UG)	JMU B (UG)	0	10	10	20
Minnesota B	Iowa State	0	0	10	10
Arizona State	Minnesota C	10	0	10	20
Michigan A	Michigan C	0	0	10	10
Ohio State B	Ohio State A	0	0	0	0
Haverford	Columbia C	0	0	0	0
John Jay	NYU A	10	0	10	20
Penn	Columbia B	0	0	10	10
Vassar	Rowan	0	0	0	0
Brandeis A	Boston University	0	0	10	10