Arrays & Strings

Question 1

Amortized insertion runtime

Answer 1

O(1)

Question 2

Why is insertion runtime amortized?

Answer 2

Doubling the size of an array happens, but the next time it happens won’t be for a while. Which describes the insertion. It will have to perform O(n) operations to insert, but the next time it happens won’t be for a while.

Question 3

Why is concatenation bad in languages that use it on strings?

Answer 3

Because a new string is created, then each character is copied over. i.e. First iteration copies x characters, second iteration copies 2x characters

Question 4

What is the runtime of string concatenation?

Answer 4

O(n^2)

Question 5

Are strings mutable in Java?

Answer 5

No, strings cannot be changed.

Question 6

What is an array?

Answer 6

contiguous place in memory that holds items of equal size and is indexed by integers

Question 7

Access of an array?

Answer 7

Constant O(1) : possible through index

Question 8

What is runtime of writing to an array?

Answer 8

Constant O(1) : possible through index

Question 9

How is an array constant access?

Answer 9

The value is found via this equation (memory_address + element_size x (index - first_index) done in the compiler

Question 10

Memory of an array?

Answer 10

O(n) space

Question 11

Delete at index of array? Not at end

Answer 11

O(n) to move all elements in array

Question 12

Insert at index? Not at end

Answer 12

O(n) to shift all elements in array