2022 p1 Flashcards
Big-O time complexity for Bubble sort
O(n^2)
Big-O time complexity for Linear search
O(n)
Big-O time complexity for Merge sort
O(nlogn)
Describe the method that would need to be followed to attempt to remove an item from a circular queue implemented as a static data structure using an array
- check if the queue is empty by comparing the front and rear pointer. if equal, the queue is empty and no item can be removed.
- if not empty, remove the front item from the front of the queue.
- update the front pointer to the next item in the queue. if the front pointer exceeds the size of the array, reset it to 0.
- reduce the count of items in the queue by 1
three differences between dynamic and static data structures
static data structures memory are allocated at compile time/dynamic data structure memory are allocated at run time.
static data structure size is fixed and cannot change during runtime/ dynamic data structure size can be changed during runtime
static data structure memory is managed by compiler/ dynamic data structure memory is managed by the programmer
explain how a single stack can be used to reverse the order of the items in a queue
- deque all the items from the queue and push them onto the stack
- pop them off one by one and enqueue them back into the original queue
- the order of the items in the queue will be reversed