Big-O Notation
Find the big-O notation for the function:
f(n) = 8n^2 - 2n
What is O(n^2)?
This data structure has a fixed length.
What is an Array?
The part of a linked list that contains the data.
What is a node?
What is the term for the principle that defines a stack where the last element added is the first to be removed?
What is "Last-In, First-Out (LIFO)"?
In an ArrayList, this method appends the certain element to the end of the list.
What is add(E element)?
Find the big-O notation for the function:
f(n) = 5n^3 + 3^nlog(n)
What is O(3^nlog(n))?
This data structure uses reallocation to make space for more elements.
What is an ArrayList?
This type of linked list has a starting node but no ending node.
What is a Single LinkedList?
In a stack, what is the term for the method that looks at the element at the top without actually removing it?
What is peek?
In a LinkedList, this method retrieves and removes the head of list.
What is remove()?
The big-O notation of n^2 usually comes from this piece of code.
What is a nested for loop?
When adding an element at a specific index in an ArrayList, we need to shift the elements over this way.
What is the right?
In a Double LinkedList, this type of traversal allows you to navigate both forward and backward.
What is bidirectional traversal?
What is the primary operation performed on a queue where an element is removed from the front of the queue?
What is poll?
In a Queue, offer inserts the specific element here.
What is the end, rear or tail?
Find T(n) and big-O notation for the function:
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
for(int k = 0; k<n; k++){
Simple Statement
Simple Statement
Simple Statement
}
}
}
What is T(n)=3n^3 and O(n^3)?
This happens when we try to add an element to a full Array.
What is an error or exception?
This type of operation involves adding an element to the end of a singly linked list.
What is appending?
In a Deque, offer adds an element here.
What is rear or tail?
What is the head, front or beginning?
Find C, 𝑛0, and f(n):
𝑇(𝑛) = 2𝑛^3 − 2𝑛^2 + 10𝑛 − 15 <= 2𝑛^3 + 2𝑛^3 + 10𝑛^3 + 0𝑛^3
What is C=14, 𝑛0= 1 and f(n)= 𝑛^3?
These methods usually execute in constant time for ArrayLists.
What are the set and get methods?
To find the nth node in a linked list, you would need to traverse through how many nodes?
What is n nodes?
The poll method removes an element here in a Deque.
What is the head or front?
In a Deque this method retrieves and removes the head of the deque.
What is poll()?