Approaching Problems & Algorithm Complexity

Decomposing Problems

Breaking down a complex task into manageable parts that can be solved independently.

Transforming Problems

Converting a specific problem into a generic problem with a known solution.

Creating Traces

Manually working through the steps to solve the problem using specific data inputs to identify decisions and process steps that can be converted into a flowchart

Time Complexity

Measures how efficient an algorithm is based on the number of instructions a computer executes to get a result.

Complexity Analysis

Quantifies an algorithm's time and space usage in relation to the input size.

Worst-Case Time Complexity

The time taken in the worst possible input scenario.

Space Complexity

A metric that indicates how much memory an algorithm uses.

Asymptotic Analysis

Uses Big O notation to classify algorithms according to how their run time or space requirements grow as the input size grows.

Constant Time - O(1)

Algorithms where the execution time does not depend on the input size; they take the same time regardless.

Linear Time - O(n)

Algorithms where the execution time grows linearly with the size of the input; each element in the input increases the execution time proportionally.

Logarithmic Time - O(log n)

Algorithms where the execution time grows logarithmically with the input size, commonly found improving algorithms by reducing the amount of needed steps.

Quadratic Time - O(n^2)

Algorithms where the execution time grows quadratically with the size of the input, common in algorithms that perform actions for all pairs of elements.

Flowchart

A visual representation of a process, using different shapes to represent steps and decisions.

Recursion

A method of problem-solving where a function calls itself directly or indirectly.

Divide and Conquer

A problem-solving technique that involves breaking down a problem into smaller subproblems, solving each subproblem independently, and then combining the solutions to solve the original problem.

Tree

A data structure that consists of nodes where each node has a value and pointers to its children.

Binary Tree

A tree data structure where each node has at most two children, which are referred to as the left child and the right child.

Binary Search Tree

A sorted binary tree data structure, which ensures efficient search, insertion, and deletion operations.

Graph

A data structure with non-linear relationships between elements represented as nodes connected by edges.

Depth-First Search (DFS)

A searching algorithm that starts at the root node and explores each branch as far as possible before backtracking.

Decomposition

Breaking down a complex task into manageable parts that can be solved independently.

Recursive Decomposition

Finding a self-similar problem that's easier to solve, often leading to recursion.

Problem Transformation

Recognizing problem patterns and converting the specific problem into a generic one with a known solution.

Algorithm Design

Converting a specific problem into a generic problem with a known solution.

Finding the Oldest User Example

Minimum/maximum aggregation problem.

Creating Traces

Manually working through the steps to solve the problem using specific data inputs.

Purpose of Traces

Reveals decisions and process steps that can be converted into a flowchart.

Time Complexity

Measures how efficient an algorithm is based on the number of instructions a computer executes to get a result.

Lowest

Aim for algorithms with the possible complexity to minimize computation time and hardware resource use.

Complexity Analysis

Quantifies an algorithm's time and space requirements.

Complexity

Expressed in terms of the input, describing how the time/space grows as a function of the input.

Worst-Case Time Complexity

The time taken in the worst-case scenario.

Sub-problem Decomposition

Breaking a problem into smaller, manageable parts.

Recursion in Problem Solving

Finding easier, self-similar problems for recursive solutions.

Pattern Recognition in Algorithms

Converting a specific problem into a known generic one.

Minimum/Maximum Aggregation

Converting a problem of finding the oldest user into finding the maximum value in a list.

Manual Tracing Process

Detailing each step explicitly as if explaining to a robot.

Pattern Identification via Traces

Using manual processes to find generic patterns previously missed.

Importance of Complexity Analysis

Essential for determining when to choose a more efficient algorithm.

Quantifying Algorithm Efficiency

Time and space requirements relative to input size.

Understanding Worst-Case Scenarios

Analyzing performance under the most demanding conditions.

Measuring Algorithm Efficiency

An algorithm's efficiency based on executed instructions.

Problem Transformation

The process of turning a specific problem into a more general form that is already solved.

Recursion

The method of solving problems by repeating a process. Each step is a smaller version of the original problem.

Algorithm Performance

Helps programmers to choose the best algorithm based on time and space required.