Computer Science Data Structures Big O Notation
0.0(0)
Studied by 65 people0.0(0)
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt PlayCard Sorting
1/41
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)
Note 
Flashcards (42)