CSC-230 Recursion, Sorting Algorithms, and Data Structures Key Concepts

What are the 3 key components of a recursive algorithm?

Decomposition, Composition, Base/stopping case

What is a base case in recursion?

A condition that stops recursion without making a recursive call

What is the factorial formula recursively?

factorial(0) = 1; factorial(n) = n × factorial(n-1)

What is tail recursion?

When there are NO pending operations after returning from a recursive call

What is the Fibonacci sequence formula?

fib(0) = 0; fib(1) = 1; fib(n) = fib(n-1) + fib(n-2)

What happens if a recursive function has no base case?

Infinite recursion / stack overflow error

What is the time complexity of recursive factorial?

O(n)

What is the time complexity of naive recursive Fibonacci?

O(2^n)

What is the time complexity of binary search (recursive)?

Best case: O(1); Worst case: O(log n)

What is the time complexity of Tower of Hanoi?

O(2^n)

How does Selection Sort work?

Partition into sorted/unsorted parts; select smallest element from unsorted

What is the time complexity of Selection Sort?

O(n²) for all cases

How does Insertion Sort work?

Divide into sorted/unsorted; insert first unsorted element into sorted part

What is the time complexity of Insertion Sort?

Best case: O(n); Average/Worst case: O(n²)

How does Bubble Sort work?

Compare adjacent elements and swap if out of order

What is the time complexity of Bubble Sort?

Best case: O(n); Worst case: O(n²)

How to optimize Bubble Sort?

Use a 'swapped' flag to terminate early if no swaps occur

What approach does Merge Sort use?

Divide-and-conquer approach

What are the 3 main steps of Merge Sort?

Divide, Conquer, Combine

What is the time complexity of Merge Sort?

O(n log n) for all cases

What is a disadvantage of Merge Sort?

Requires extra space O(n)

How does Quick Sort work?

Pick pivot, partition elements, recursively sort sub-arrays

What is the time complexity of Quick Sort?

Best/Average: O(n log n); Worst: O(n²)

How to improve Quick Sort pivot selection?

Use median-of-three method

Which sorting algorithms sort 'in place'?

Selection Sort, Insertion Sort, Bubble Sort, Quick Sort

What is a Linked List?

A sequence of nodes with data and a pointer to the next node

What are the components of a singly linked list node?

Data portion and next pointer

What does the last node in a Linked List point to?

null

What are the advantages of Linked Lists over Arrays?

Dynamic size, easy insertion/deletion, no contiguous memory required

What are the steps to insert at the front of a linked list?

Make new node point to first node, update front to new node

What are the steps to insert at the end of a linked list?

Locate last node, make new node point to null, update last node

What are the steps to delete the first node in a linked list?

Make front point to second node

What is a Stack?

LIFO data structure

What are the 3 basic operations of a Stack?

push, pop, peek

What are some use cases for Stacks?

Method call stack, expression evaluation, undo functionality

What is a Queue?

FIFO data structure

What are the 3 basic operations of a Queue?

add (enqueue), remove (dequeue), peek

What are some use cases for Queues?

Print job queues, process scheduling, waiting lines

What does Big O notation represent?

Upper bound on worst-case running time

What is the time complexity of nested loops (both go 0 to n)?

O(n²)

What is the divide-and-conquer paradigm?

Divide problem, conquer sub-problems, combine solutions

What does binary search return on a failed search?

-insertion_point - 1

Which sorting algorithm has the best performance?

Merge Sort: O(n log n) guaranteed