Big-O and Data Structures

What does Big-O notation describe about an algorithm?

• Exact seconds
• Growth of time/memory
• Code length
• Screen size

Which growth rate is the fastest (most efficient)?

• O(n²)
• O(1)
• O(2ⁿ)
• O(n)

Typical efficient sorting runs in ____ time.

• O(n²)
• O(1)
• O(n log n)
• O(2ⁿ)

Big-O describes the best case unless stated otherwise.

• True
• False

Accessing an array element by index takes:

• O(log n)
• O(n)
• O(n²)
• O(1)

Inserting in the middle of an array takes:

• O(2ⁿ)
• O(log n)
• O(1)
• O(n)

A linked list stores each element with a ____ to the next node.

• index
• pointer
• root
• hash

A stack follows Last-In, First-Out (LIFO) order.

• True
• False

A queue follows ____ order, like a line of people.

• LIFO
• random
• FIFO
• sorted

Push and pop operations on a stack run in:

• O(n)
• O(n²)
• O(1)
• O(log n)

A balanced binary search tree searches in:

• O(n)
• O(2ⁿ)
• O(1)
• O(log n)

In a binary search tree, larger values go to the left.

• True
• False

Which are examples of balanced trees?

• Hash, heap
• Stack, queue
• AVL, red-black
• Array, list

A hash table uses a ____ function to turn a key into an index.

• sort
• root
• pointer
• hash

When two keys produce the same index, this is called a:

• balance
• collision
• rotation
• overflow