Big O CPE/CSC 202 Hatalsky Cal Poly

studied byStudied by 0 people
0.0(0)
learn
LearnA personalized and smart learning plan
exam
Practice TestTake a test on your terms and definitions
spaced repetition
Spaced RepetitionScientifically backed study method
heart puzzle
Matching GameHow quick can you match all your cards?
flashcards
FlashcardsStudy terms and definitions

1 / 97

encourage image

There's no tags or description

Looks like no one added any tags here yet for you.

98 Terms

1

O(n)

Starting with an empty heap, add (enqueue) n elements one at a time to build a binary heap (smallest)

New cards
2

O(1)

Get (but do not delete) the minimum item from a minimum heap (smallest)

New cards
3

O(n)

Perform insertion sort on an already sorted set of data (smallest)

New cards
4

O(nlogn)

Perform a Heap sort on a random set of data (smallest)

New cards
5

O(n^2)

Perform a Quick sort on a sorted set of data if the first item is always chosen as the pivot (smallest)

New cards
6

O(n)

Perform a post order traversal of a binary tree (smallest)

New cards
7

O(n)

Estimate for the worst case of finding the minimum in a Binary Search Tree (smallest)

New cards
8

O(nlogn)

Estimate for the worst case for adding (enqueueing) n items into a priority queue (smallest)

New cards
9

O(n)

Find the minimum key/value in a hash table (smallest)

New cards
10

O(n)

Find the height of a Binary Search Tree as implemented in lab 5 (smallest)

New cards
11

O(n)

Given a list of length n, build a binary heap using the bottom up construction method (smallest)

New cards
12

O(logn)

Delete (dequeue) the maximum item from a maximum binary heap (smallest)

New cards
13

O(1)

Add an item to a Hash Table (assume an efficient implementation of the hash table) (smallest)

New cards
14

O(logn)

Remove an item from a binary search tree (smallest)

New cards
15

O(nlogn)

Perform mergesort on a random set of data (smallest)

New cards
16

O(n)

Find an arbitrary item in an array (smallest)

New cards
17

O(1)

Delete the last (tail) node from a doubly linked list with a sentinel node implementation (smallest)

New cards
18

O(n)

Delete the last item from a singly linked list (assume only a reference to the head of the list) (smallest)

New cards
19

O(1)

Add an element to the end of an array (assume array has room for element) (smallest)

New cards
20

O(1)

Delete the first item from a singly linked list (assume only a reference to the head of the list) (smallest)

New cards
21

O(logn)

Find an arbitrary item in a well-balance binary search tree (smallest)

New cards
22

O(n^2)

Delete n elements form an array by repeatedly removing the first element (at index 0) (smallest)

New cards
23

O(n)

Insert and item at the beginning of an array (add at index 0) (smallest)

New cards
24

O(n)

Insertion sort (best case)

New cards
25

O(n^2)

Insertion sort (worst case)

New cards
26

O(n^2)

Insertion sort (average case)

New cards
27

O(n^2)

Selection sort (best case)

New cards
28

O(n^2)

Selection sort (worst case)

New cards
29

O(n^2)

Selection sort (average case)

New cards
30

O(nlogn)

Mergesort (best case)

New cards
31

O(nlogn)

Mergesort (worst case)

New cards
32

O(nlogn)

Mergesort (average case)

New cards
33

O(nlogn)

Quicksort (average case)

New cards
34

O(nlogn)

Quicksort (best case)

New cards
35

O(nlogn)

Quicksort (worst case)

New cards
36

O(nlogn)

Heapsort (best case)

New cards
37

O(nlogn)

Heapsort (average case)

New cards
38

O(nlogn)

Heapsort (worst case)

New cards
39

O(n)

Add at the beginning of an array-based list (average)

New cards
40

O(1)

Add at the beginning of a link-based list (average)

New cards
41

O(n)

Add at the end of a link-based list (average)

New cards
42

O(1)

Get() array-based list (average)

New cards
43

O(n)

get() Link-based list

New cards
44

O(n)

Remove from beginning array-based list

New cards
45

O(1)

Remove from beginning link-based list

New cards
46

O(n)

Stack search (worst case)

New cards
47

O(n)

Stack search (average case)

New cards
48

O(1)

Stack push (worst case)

New cards
49

O(1)

Stack push (average case)

New cards
50

O(1)

Stack pop (worst case)

New cards
51

O(1)

Stack pop (average case)

New cards
52

O(n)

Number of items in a link-based list

New cards
53

O(1)

Number of items in a link-based list with a size attribute

New cards
54

O(1)

Dequeue item from link-based queue

New cards
55

O(1)

Enqueue item into link-based queue

New cards
56

O(1)

Dequeue item from circular array-based queue

New cards
57

O(1)

Enqueue item into circular array-based queue

New cards
58

O(n)

Add item to the beginning of an array-based list (ADT)

New cards
59

O(n)

Add item to the middle of an array-based list (ADT)

New cards
60

O(1)

Add item to the end of an array-based list (ADT)

New cards
61

O(1)

Add item to the beginning of a link-based list (ADT)

New cards
62

O(n)

Add item to the middle of a link-based list (ADT)

New cards
63

O(1)

Add item to the end of a link-based list (ADT)

New cards
64

O(n)

Remove item from the beginning of an array-based list (ADT)

New cards
65

O(n)

Remove item from the middle of an array-based list (ADT)

New cards
66

O(1)

Remove item from the end of an array-based list (ADT)

New cards
67

O(1)

Remove item from the beginning of a (doubly) link-based list (ADT)

New cards
68

O(n)

Remove item from the middle of a link-based list (ADT)

New cards
69

O(1)

Remove item from the end of a link-based list with sentinel node (ADT)

New cards
70

O(n)

Find a value in an array-based list

New cards
71

O(n)

Find a value in a link-based list

New cards
72

O(1)

Find the size of an array-based list

New cards
73

O(1)

Get an item based on index an array-based list

New cards
74

O(1)

Set an index to a value in an array-based list

New cards
75

O(1)

Find the size of a link-based list

New cards
76

O(n)

Get an item based on index a link-based list

New cards
77

O(n)

Set an index to a value in a link-based list

New cards
78

O(n)

Search for a value in a doubly-linked list (average)

New cards
79

O(1)

Insert a value in a doubly-linked list (average)

New cards
80

O(1)

Delete a value in a doubly-linked list (average)

New cards
81

O(n)

Search for a value in a doubly-linked list (worst)

New cards
82

O(1)

Insert a value in a doubly-linked list (worst)

New cards
83

O(1)

Delete a value in a doubly-linked list (worst)

New cards
84

O(logn)

Search for a value in a Binary Search tree (average)

New cards
85

O(logn)

Insert a value in a Binary Search tree (average)

New cards
86

O(logn)

Delete a value in a Binary Search tree (average)

New cards
87

O(n)

Search for a value in a Binary Search tree (worst)

New cards
88

O(n)

Insert a value in a Binary Search tree (worst)

New cards
89

O(n)

Delete a value in a Binary Search tree (worst)

New cards
90

O(n)

Enqueue all n items into a Binary Heap

New cards
91

O(nlogn)

Dequeue all n items from a Binary Heap

New cards
92

O(nlogn)

Heap sort

New cards
93

O(n)

Bottom up heap creation

New cards
94

O(1)

Insert an item into a hash table

New cards
95

O(1)

Find an item in a hash table

New cards
96

O(1)

Insert an item into a Hash Table that uses separate chaining (very small linked list)

New cards
97

O(1)

Find an item in a Hash Table that uses separate chaining (very small linked list)

New cards
98

O(1)

Remove an item from a Hash Table that uses separate chaining (very small linked list)

New cards

Explore top notes

note Note
studied byStudied by 64 people
213 days ago
4.7(3)
note Note
studied byStudied by 26 people
891 days ago
5.0(1)
note Note
studied byStudied by 25 people
514 days ago
5.0(1)
note Note
studied byStudied by 4 people
688 days ago
5.0(1)
note Note
studied byStudied by 16 people
903 days ago
5.0(1)
note Note
studied byStudied by 10 people
760 days ago
5.0(1)
note Note
studied byStudied by 67 people
701 days ago
5.0(4)
note Note
studied byStudied by 44 people
758 days ago
5.0(3)

Explore top flashcards

flashcards Flashcard (92)
studied byStudied by 11 people
841 days ago
4.0(1)
flashcards Flashcard (116)
studied byStudied by 10 people
800 days ago
5.0(1)
flashcards Flashcard (43)
studied byStudied by 15 people
3 days ago
5.0(1)
flashcards Flashcard (57)
studied byStudied by 17 people
751 days ago
5.0(2)
flashcards Flashcard (40)
studied byStudied by 2 people
177 days ago
5.0(1)
flashcards Flashcard (71)
studied byStudied by 42 people
385 days ago
5.0(4)
flashcards Flashcard (82)
studied byStudied by 41 people
88 days ago
5.0(1)
flashcards Flashcard (222)
studied byStudied by 29 people
646 days ago
5.0(1)
robot