Big O Notations - Data Structures Flashcards

Question 1

Q

Array

Answer

A

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

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

Space (worst case): Θ(n)

Question 2

Q

Stack

Answer

A

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

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

Space (worst case): Θ(n)

Question 3

Q

Queue

Answer

A

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

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

Space (worst case): Θ(n)

Question 4

Q

Singly-Linked List

Answer

A

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

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

Space (worst case): Θ(n)

Question 5

Q

Doubly-Linked List

Answer

A

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

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

Space (worst case): Θ(n)

Question 6

Q

Skip List

Answer

A

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

Worst Case
    Access: Θ(n)
    Search: Θ(n)
    Insertion: Θ(n)
    Deletion: Θ(n)

Space (worst case): Θ(log(n))

Question 7

Q

Hash Table (Dictionary)

Answer

A

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

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

Space (worst case): Θ(n)

Question 8

Q

Binary Search Tree

Answer

A

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

Worst Case
    Access: Θ(n)
    Search: Θ(n)
    Insertion: Θ(n)
    Deletion: Θ(n)

Space (worst case): Θ(n)

Question 9

Q

Cartesian Tree

Answer

A

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

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

Space (worst case): Θ(n)

Question 10

Q

B-Tree

Answer

A

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

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

Space (worst case): Θ(n)

Question 11

Q

Red-Black Tree

Answer

A

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

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

Space (worst case): Θ(n)

Question 12

Q

Splay Tree

Answer

A

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

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

Space (worst case): Θ(n)

Question 13

Q

AVL Tree

Answer

A

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

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

Space (worst case): Θ(n)

Question 14

Q

KD Tree

Answer

A

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

Worst Case
    Access: Θ(n)
    Search: Θ(n)
    Insertion: Θ(n)
    Deletion: Θ(n)

Space (worst case): Θ(n)

Brainscape's Knowledge GenomeTM

Big O Notations - Data Structures Flashcards

Brainscape's Knowledge Genome^TM