Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Computer Science > Big O Cheat Sheet > Flashcards

Big O Cheat Sheet Flashcards

1
Q

Analyze the complexity:

Array

Average

A

Access: Θ(1)
Search: Θ(n)
Insertion: Θ(n)
Deletion: Θ(n)

Space: O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Analyze the complexity:

Array

Worst

A

Access: O(1)
Search: O(n)
Insertion: O(n)
Deletion: O(n)

Space: O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Analyze the complexity:

Stack

Average

A

Access: Θ(n)
Search: Θ(n)
Insertion: Θ(1)
Deletion: Θ(1)

Space: O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Analyze the complexity:

Stack

Worst

A

Access: O(n)
Search: O(n)
Insertion: O(1)
Deletion: O(1)

Space: O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Analyze the complexity:

Queue

Average

A

Access: Θ(n)
Search: Θ(n)
Insertion: Θ(1)
Deletion: Θ(1)

Space: O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Analyze the complexity:

Queue

Worst

A

Access: O(n)
Search: O(n)
Insertion: O(1)
Deletion: O(1)

Space: O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Analyze the complexity:

Singly-Linked List

Average

A

Access: Θ(n)
Search: Θ(n)
Insertion: Θ(1)
Deletion: Θ(1)

Space: O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Analyze the complexity:

Singly-Linked List

Worst

A

Access: O(n)
Search: O(n)
Insertion: O(1)
Deletion: O(1)

Space: O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Analyze the complexity:

Doubly-Linked List

Average

A

Access: Θ(n)
Search: Θ(n)
Insertion: Θ(1)
Deletion: Θ(1)

Space: O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Analyze the complexity:

Doubly-Linked List

Worst

A

Access: O(n)
Search: O(n)
Insertion: O(1)
Deletion: O(1)

Space: O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Analyze the complexity:

Skip List

Average

A

Access: Θ(log(n))
Search: Θ(log(n))
Insertion: Θ(log(n))
Deletion: Θ(log(n))

Space: O(n log(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Analyze the complexity:

Skip List

Worst

A

Access: O(n)
Search: O(n)
Insertion: O(n)
Deletion: O(n)

Space: O(n log(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Analyze the complexity:

Hash Table

Average

A

Access: N/A
Search: Θ(1)
Insertion: Θ(1)
Deletion: Θ(1)

Space: O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Analyze the complexity:

Hash Table

Worst

A

Access: N/A
Search: O(n)
Insertion: O(n)
Deletion: O(n)

Space: O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Analyze the complexity:

Binary Search Tree

Average

A

Access: Θ(log(n))
Search: Θ(log(n))
Insertion: Θ(log(n))
Deletion: Θ(log(n))

Space: O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Analyze the complexity:

Binary Search Tree

Worst

A

Access: O(n)
Search: O(n)
Insertion: O(n)
Deletion: O(n)

Space: O(n)

17
Q

Analyze the complexity:

Cartesian Tree

Average

A

Access: N/A
Search: Θ(log(n))
Insertion: Θ(log(n))
Deletion: Θ(log(n))

Space: O(n)

18
Q

Analyze the complexity:

Cartesian Tree

Worst

A

Access: N/A
Search: O(n)
Insertion: O(n)
Deletion: O(n)

Space: O(n)

19
Q

Analyze the complexity:

B-Tree

Average

A

Access: Θ(log(n))
Search: Θ(log(n))
Insertion: Θ(log(n))
Deletion: Θ(log(n))

Space: O(n)

20
Q

Analyze the complexity:

B-Tree

Worst

A

Access: O(log(n))
Search: O(log(n))
Insertion: O(log(n))
Deletion: O(log(n))

Space: O(n)

21
Q

Analyze the complexity:

Red-Black Tree

Average

A

Access: Θ(log(n))
Search: Θ(log(n))
Insertion: Θ(log(n))
Deletion: Θ(log(n))

Space: O(n)

22
Q

Analyze the complexity:

Red-Black Tree

Worst

A

Access: O(log(n))
Search: O(log(n))
Insertion: O(log(n))
Deletion: O(log(n))

Space: O(n)

23
Q

Analyze the complexity:

Splay Tree

Average

A

Access: N/A
Search: Θ(log(n))
Insertion: Θ(log(n))
Deletion: Θ(log(n))

Space: O(n)

24
Q

Analyze the complexity:

Splay Tree

Worst

A

Access: N/A
Search: O(log(n))
Insertion: O(log(n))
Deletion: O(log(n))

Space: O(n)

25
Q

Analyze the complexity:

AVL Tree

Average

A

Access: Θ(log(n))
Search: Θ(log(n))
Insertion: Θ(log(n))
Deletion: Θ(log(n))

Space: O(n)

26
Q

Analyze the complexity:

AVL Tree

Worst

A

Access: O(log(n))
Search: O(log(n))
Insertion: O(log(n))
Deletion: O(log(n))

Space: O(n)

27
Q

Analyze the complexity:

KD Tree

Average

A

Access: Θ(log(n))
Search: Θ(log(n))
Insertion: Θ(log(n))
Deletion: Θ(log(n))

Space: O(n)

28
Q

Analyze the complexity:

KD Tree

Worst

A

Access: O(n)
Search: O(n)
Insertion: O(n)
Deletion: O(n)

Space: O(n)

Computer Science (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions