Chapter 2: Arrays Flashcards
1
Q
Ordered Arrays: Advantages and Disadvantages
A
Search is faster, insertion is slower (deletion and insertion are slow in both ordered an unordered)
2
Q
Logarithms
A
log base 2 of n is the number of times it is required to divide n by 2 to get 1.
3
Q
Big O: Insertion into an unordered array
A
O(1)
4
Q
Big O: Linear search
A
O(n)
5
Q
Big O: Binary search
A
log(n)
6
Q
Why not use arrays for everything?
A
Insertion into an unordered array takes O(1), but searching takes O(n), for an ordered array, insertion takes O(n) and searching O(logn). For both unordered and ordered, deletion takes O(n) time.
7
Q
Operations on arrays
A
Insertion, deletion, and searching
