2.3 Algorithms

Question 1

What is the Big-O notation for the time complexity of linear and binary
searches? (2.3.1)

Answer 1

Linear: O(n)

Binary: O(log(n))

Question 2

How do breadth-first and depth-first traversals differ? (2.3.1)

Answer 2

Breadth:

• Visits every level
• Uses queues
• Minimal edge visits
• Suitable when nodes closer

Depth:

• Visits up to leaf
• Uses stacks
• May traverse more edges
• Suitable when nodes further

Question 3

What are the time complexity Big-O notations for bubble, insertion, merge, and
quick sorts? (2.3.1)

Answer 3

Bubble: O(n2)

Insertion: O(n2)

Merge: worst-case O(n logn)

Quick: O(n2)

Question 4

What are time and space complexity? (2.3.1)

Answer 4

Time:

• Algorithms time required solving particular problem
• Shows time relative to amount of data elements inputted

Space:

• Storage algorithm takes
• Algorithms store extra data making copies

Question 5

How does a depth-first post-order traversal work? (2.3.1)

Answer 5

• Goes as far into tree as possible before backtracking
• Uses stack, goes left child node of current node
• Goes right child
• If no child, visits current node
• Backtracks to next stacked node, moves right

Question 6

How do quick sorts work? (2.3.1)

Answer 6

• Selects central element (pivot), divides input around it
• Divided by size to left/right of pivot
• Process repeated recursively until all pivoted, or 1 item in list