WEEK 3 Time Complexity and Asymptotic Notation

These flashcards cover key concepts related to time complexity and algorithms from the lecture notes.

Time Complexity

A computational metric that describes the amount of time an algorithm takes to complete as a function of the length of the input.

Asymptotic Notation

Mathematical notation used to describe the limiting behavior of a function, particularly in the context of algorithms.

Selection Sort

A sorting algorithm that repeatedly finds the smallest element from the unsorted portion and moves it to the front.

Binary Search

An efficient algorithm for finding an item from a sorted list that repeatedly divides the search interval in half.

Big-Oh Notation

A mathematical notation used to describe the upper bound of an algorithm's running time in terms of input size.

Primitive Operations

Basic operations such as comparisons or swaps that are counted when analyzing the time complexity of an algorithm.

O(n^2)

Big-Oh notation indicating that the time complexity grows quadratically as the input size increases.

O(log n)

Big-Oh notation indicating that the time complexity grows logarithmically as the input size increases.

Polynominal Time

An algorithm is said to run in polynomial time if the number of steps required is O(n^k) for some non-negative integer k.

NP-Complete Problems

A class of problems for which no known polynomial-time algorithms exist, but any proposed solutions can be verified quickly.

P vs NP Problem

An unsolved question in computer science asking whether every problem whose solution can be quickly verified can also be quickly solved.

Exhaustive Search

A brute-force approach that checks all possible solutions until the correct one is found, typically inefficient for large inputs.

Non-Computable Problems

Problems that cannot be solved by any algorithm on a computer.

Computable Problems

Problems that can be solved using a computer algorithm.

Recursive Algorithm

An algorithm that solves a problem by solving smaller instances of the same problem.

Algorithmic Complexity

A measure of the amount of resources (like time and space) that an algorithm requires to process data.