l i b

so apparently, the amortized cost of extending a dynamic array is O(n).

amortized means average.

an array screams at you if you try to add an element that makes its size bigger than what it was originally initialized with.

a dynamic array automatically handles adding capacity.

worst case

the worst case for extending a dynamic array is O(n^2).

here's what that looks like:

say you have an array of size three with three elements -> [1][2][3]

adding another element looks like this:

we went over each element, so the time complexity is O(n).

if we have n elements where we do this every time, the time complexity is O(n * n) or O(n^2).

but, we aren't really going over each element every time.

proof

let's start with an array of size 1 -> [ ]. we'll be adding integers starting from 1 -> 1,2,3,4,5,6,7,8.

adding 1:

the number of operations is 1 because we added 1.

adding 2:

the number of operations is 2 because we copied over 1 and added 2.

adding 3:

the number of operations is 3 because we copied over 1 and 2 then added 3.

adding 4:

the number of operations is 1 because we only need to add 4.

adding 5:

the number of operations is 5 because we copied over 1 through 4, then added 5.

adding 6: number of operations (1)

the number of operations is 1.

adding 7: number of operations (1)

the number of operations is 1.

adding 8: number of operations (1)

the number of operations is 1.

using the above as a reference, we could look at the number of operations as input size grows by adding the number of operations when adding the nth element to the sum of the number of operations that occurred one input size below. here's what that looks like:

input size number of operations number of operations in terms of n
1 1 n
2 1 + 2 = 3 n + 1
3 3 + 3 = 6 n + 3
4 6 + 1 = 7 n + 3
5 7 + 5 = 12 n + 7
6 12 + 1 = 13 n + 7
7 13 + 1 = 14 n + 7
8 14 + 1 = 15 n + 7

we could see that the increase in the number of operations as input grows is kind of slow.

we could also see that the time complexity is O(n).