Computer Science Data Structures Big O Notation

0.0(0)
studied byStudied by 65 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/41

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

42 Terms

1
New cards
O(1)
Constant (fastest speed)
2
New cards
O(log N)
Logarithmic (2nd fastest speed)
3
New cards
O(N)
Linear (3rd fastest speed)
4
New cards
O(N log N)
Linearithmic (3rd slowest speed)
5
New cards
O(N^2)
Quadratic (2nd slowest speed)
6
New cards
O(2^N)
Exponential (slowest speed)
7
New cards
Traversing the Array
O(N)
8
New cards
Search for an item unknown in an Array
O(N) or O(log N)
9
New cards
Remove any item location unknown in an Array
O(N)
10
New cards
Get any item location unknown in an Array
O(1)
11
New cards
Add item at the end of an Array
O(1)
12
New cards
Add item at the front of an Array
O(N)
13
New cards
Traversing an array in a Linked List
O(N)
14
New cards
Search for an item in a Linked List
O(N)
15
New cards
Remove any item location unknown in a Linked List
O(N)
16
New cards
Add item at the end of a Linked List
O(N)
17
New cards
Add item at the front of a Linked List
O(1)
18
New cards
Add item at the end of a Double Linked List (almost every property is identical to Linked List except this)
O(1)
19
New cards
Traversing an array in a Binary (Search) Tree
O(N)
20
New cards
Search for an item in a Binary (Search) Tree
O(log N)
21
New cards
Remove any item location unknown in a Binary (Search) Tree
O(log N)
22
New cards
Get any item location unknown in a Binary (Search) Tree
O(log N)
23
New cards
Add item at the end of a Binary (Search) Tree
O(log N)
24
New cards
Add item at the front of a Binary (Search) Tree
O(1)
25
New cards
Traversing an array in an ArrayList
O(N)
26
New cards
Search for an item in an ArrayList
O(log N) or O(N)
27
New cards
Remove any item location unknown in an ArrayList
O(N)
28
New cards
Get any item location unknown in an ArrayList
O(1)
29
New cards
Add item at the end of an ArrayList
O(1)
30
New cards
Add item at the front of an ArrayList
O(N)
31
New cards
"add" / "remove" / "contains" in a Tree Set
O(log N)
32
New cards
"put" / "get / "containsKey" in a Tree Map
O(log N)
33
New cards
"add" / "remove" / "contains" in a Hash Set
O(1)
34
New cards
"put" / "get / "containsKey" in a Hash Map
O(1)
35
New cards
Best/Average/Worst Case for Linear Search
O(1) / O(N) / O(N)
36
New cards
Best/Average/Worst Case for Binary Search
O(1) / O(log N) / O(log N)
37
New cards
Best/Average/Worst Case for Selection Sort
O(N^2)
38
New cards
Best/Average/Worst Case for Bubble Sort
O(N^2)
39
New cards
Best/Average/Worst Case for Insertion Sort
O(N) / O(N^2) / O(N^2)
40
New cards
Best/Average/Worst Case for Merge Sort
O(N log N)
41
New cards
Best/Average/Worst Case for Quick Sort
O(N log N) / O(N log N) / O(N^2)
42
New cards
Best/Average/Worst Case for Heap Sort
O(N log N)