Complexity and algorithms

Algorithm

A finite set of precise instructions for performing a computation or solving a problem.

Complexity Analysis

The determination of the computational complexity of algorithms, including time and space requirements.

Asymptotic Complexity

Analysis of the upper and average complexity bounds of an algorithm as input size approaches infinity.

Pseudocode

A notation resembling a simplified programming language, used to design algorithms.

Time Complexity

A function that relates the length of an algorithm's input to the number of steps it takes to complete.

Space Complexity

A function that relates the length of an algorithm's input to the number of memory locations it uses.

Efficiency of Algorithms

The measurement of how fast an algorithm runs and how much memory it uses.

Best-case Analysis

The minimum number of steps taken on any instance of size A.

Worst-case Analysis

The maximum number of steps taken on any instance of size A.

Bubble Sort

A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Merge Sort

A divide-and-conquer algorithm that sorts a list by recursively dividing it into sublists and merging sorted sublists.

Recursion

The process in which a function calls itself directly or indirectly to solve a problem.

Input Size

The amount of data or number of elements that an algorithm processes.

Hash Table

A data structure that implements an associative array abstract data type, a structure that can map keys to values.

Binary Search

An efficient algorithm for finding an item from a sorted list of items, reducing the search space in half with each step.

Graph Representation

The method of implementing graph structures through various means such as adjacency lists or matrices.

What is an algorithm?

An algorithm is a finite set of precise instructions for performing a computation or solving a problem.

What is complexity analysis?

Complexity analysis is the determination of the computational complexity of algorithms, including time and space requirements.

What does asymptotic complexity refer to?

Asymptotic complexity analyses the upper and average complexity bounds of an algorithm as input size approaches infinity.

What is pseudocode?

Pseudocode is a notation resembling a simplified programming language, used to design algorithms.

What is time complexity?

Time complexity is a function that relates the length of an algorithm's input to the number of steps it takes to complete.

What is space complexity?

Space complexity is a function that relates the length of an algorithm's input to the number of memory locations it uses.

How is efficiency of algorithms measured?

The efficiency of algorithms is measured by how fast an algorithm runs and how much memory it uses.

What is best-case analysis?

Best-case analysis is the minimum number of steps taken on any instance of size A.

What does worst-case analysis entail?

Worst-case analysis is the maximum number of steps taken on any instance of size A.

What is bubble sort?

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.