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 A	Berkeley B	0	10	10	20
Berkeley C	Stanford B	0	0	0	0
Stanford A	Stanford C	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
Virginia B (UG)	Duke A (UG)	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
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 A (Grad)	Liberty C (DII)	10	0	10	20
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
Kenyon	Cedarville	0	0	10	10
Michigan A	Michigan C	0	0	10	10
Ohio State B	Ohio State A	0	0	0	0
Columbia A	NYU B	0	10	10	20
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
Bristol	Imperial A	0	0	0	0
Oxford C	Cambridge A	10	0	10	20
Edinburgh	Cambridge C	0	0	10	10
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
Geodesic	Georgia Tech B	0	0	10	10
Vanderbilt A	Harding	0	0	10	10
Tennessee	South Carolina	0	0	0	0
Vanderbilt B	Georgia Tech A	0	0	10	10
Brandeis A	Boston University	0	0	10	10
Dartmouth A	Brandeis B	0	0	0	0
Yale A	Harvard B	0	0	0	0