Computer Science Data Structures Big O Notation

studied byStudied by 65 people
0.0(0)
get a hint
hint

O(1)

1 / 41

encourage image

There's no tags or description

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

42 Terms

1

O(1)

Constant (fastest speed)

New cards
2

O(log N)

Logarithmic (2nd fastest speed)

New cards
3

O(N)

Linear (3rd fastest speed)

New cards
4

O(N log N)

Linearithmic (3rd slowest speed)

New cards
5

O(N^2)

Quadratic (2nd slowest speed)

New cards
6

O(2^N)

Exponential (slowest speed)

New cards
7

Traversing the Array

O(N)

New cards
8

Search for an item unknown in an Array

O(N) or O(log N)

New cards
9

Remove any item location unknown in an Array

O(N)

New cards
10

Get any item location unknown in an Array

O(1)

New cards
11

Add item at the end of an Array

O(1)

New cards
12

Add item at the front of an Array

O(N)

New cards
13

Traversing an array in a Linked List

O(N)

New cards
14

Search for an item in a Linked List

O(N)

New cards
15

Remove any item location unknown in a Linked List

O(N)

New cards
16

Add item at the end of a Linked List

O(N)

New cards
17

Add item at the front of a Linked List

O(1)

New cards
18

Add item at the end of a Double Linked List (almost every property is identical to Linked List except this)

O(1)

New cards
19

Traversing an array in a Binary (Search) Tree

O(N)

New cards
20

Search for an item in a Binary (Search) Tree

O(log N)

New cards
21

Remove any item location unknown in a Binary (Search) Tree

O(log N)

New cards
22

Get any item location unknown in a Binary (Search) Tree

O(log N)

New cards
23

Add item at the end of a Binary (Search) Tree

O(log N)

New cards
24

Add item at the front of a Binary (Search) Tree

O(1)

New cards
25

Traversing an array in an ArrayList

O(N)

New cards
26

Search for an item in an ArrayList

O(log N) or O(N)

New cards
27

Remove any item location unknown in an ArrayList

O(N)

New cards
28

Get any item location unknown in an ArrayList

O(1)

New cards
29

Add item at the end of an ArrayList

O(1)

New cards
30

Add item at the front of an ArrayList

O(N)

New cards
31

"add" / "remove" / "contains" in a Tree Set

O(log N)

New cards
32

"put" / "get / "containsKey" in a Tree Map

O(log N)

New cards
33

"add" / "remove" / "contains" in a Hash Set

O(1)

New cards
34

"put" / "get / "containsKey" in a Hash Map

O(1)

New cards
35

Best/Average/Worst Case for Linear Search

O(1) / O(N) / O(N)

New cards
36

Best/Average/Worst Case for Binary Search

O(1) / O(log N) / O(log N)

New cards
37

Best/Average/Worst Case for Selection Sort

O(N^2)

New cards
38

Best/Average/Worst Case for Bubble Sort

O(N^2)

New cards
39

Best/Average/Worst Case for Insertion Sort

O(N) / O(N^2) / O(N^2)

New cards
40

Best/Average/Worst Case for Merge Sort

O(N log N)

New cards
41

Best/Average/Worst Case for Quick Sort

O(N log N) / O(N log N) / O(N^2)

New cards
42

Best/Average/Worst Case for Heap Sort

O(N log N)

New cards

Explore top notes

note Note
studied byStudied by 15 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 15 people
Updated ... ago
5.0 Stars(2)
note Note
studied byStudied by 28 people
Updated ... ago
5.0 Stars(2)
note Note
studied byStudied by 17 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 44 people
Updated ... ago
5.0 Stars(2)
note Note
studied byStudied by 1 person
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 8 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 93 people
Updated ... ago
5.0 Stars(1)

Explore top flashcards

flashcards Flashcard118 terms
studied byStudied by 1 person
Updated ... ago
4.0 Stars(1)
flashcards Flashcard49 terms
studied byStudied by 4 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard321 terms
studied byStudied by 79 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard753 terms
studied byStudied by 12 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard61 terms
studied byStudied by 3 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard64 terms
studied byStudied by 84 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard82 terms
studied byStudied by 10 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard83 terms
studied byStudied by 92 people
Updated ... ago
5.0 Stars(2)