CS 1332: Exam 1 Big-O Time Complexities
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt Play1/33
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai | Chat |
|---|
No analytics yet
Send a link to your students to track their progress
34 Terms
What is the worst-case time complexity of adding to a singly-linked list backed stack without a tail pointer?
O(1)
What is the worst-case cost of calling addToback (data) to a singly-linked list without a tail pointer?
O(1)
Suppose you add n elements to an array-backed stack. What is the best-case of retrieving the first element added?
O(n)
What is the worst-case time complexity of clearing a singly-linked list of size n with a tail pointer by calling removeFromBack() n times?
O(n^2)
What is the worst-case time complexity of creating a list of data of all the elements in a binary search tree from largest to smallest element?
O(n)
addToBack(T element), ArrayList
O(1)
addToFront(T element), ArrayList
O(n)
addAtIndex(int index, T element), ArrayList
O(n)
removeFromBack(), ArrayList
O(1)
removeFromFront(), ArrayList
O(n)
removeAtIndex(int index), ArrayList
O(n)
get(int index), ArrayList
O(1)
addToBack(T element), Singly-Linked List w/o tail pointer
O(n)
addToFront(T element), Singly-Linked List
O(1)
addAtIndex(int index, T element), Singly-Linked List
O(n)
removeFromBack(), Singly-Linked List w/ tail pointer
O(n)
removeFromFront(), Singly-Linked List
O(1)
removeAtIndex(int index), Singly-Linked List
O(n)
get(int index), Singly-Linked List
O(n)
addToBack(T element), Singly-Linked List w/ tail pointer
O(1)
What is the time complexity of removing the first element of an array-backed deque?
O(n)
What is the time complexity of computing the height of a binary search tree?
O(n)
What is the time complexity of accessing the largest element in a binary search tree?
O(n)
What is the time complexity of removing the third element from a linked-list backed stack?
O(1)
What is the time complexity of removing an element from a linked list-backed Queue and adding it to an array-backed Stack?
O(n)
What is the time complexity for buildHeap?
O(n)
What is the time complexity of removing a data value from a binary tree?
O(log n)
What is the time complexity of accessing a heap?
O(1)
What is the worst-case time complexity of searching an element in a Full BST?
O(n)
What is the worst-case time complexity of searching a complete BST?
O(log n)
What is the worst-case time complexity of transforming a linked list into a BST?
O(n^2)
What is the time complexity of preorder, postorder, inorder, and levelorder transversals?
O(n)
What is the time complexity to enqueue data into a full queue?
O(n)
What is the time complexity to enqueue data into a queue that is not full?
O(1)