ITE131: Data Structures and Algorithms - Asymptotic Notation

A set of vocabulary flashcards based on the concepts of asymptotic notation and algorithm analysis.

Asymptotic Analysis

A method of analyzing the performance of algorithms based on their running time and input size.

Big O Notation

A mathematical notation used to describe the upper limit of an algorithm's running time based on input size.

Worst Case Complexity

The maximum number of steps taken by an algorithm for any instance of size n.

Best Case Complexity

The minimum number of steps taken by an algorithm for the best possible instance of size n.

Quadratic Growth

A situation where the algorithm's performance is proportional to the square of the input size, represented mathematically as O(n²).

Linear Growth

A situation where the algorithm's performance is directly proportional to the input size, represented mathematically as O(n).

Polynomial Growth

A situation where the algorithm's performance is described by a polynomial expression, such as O(n^k) where k is a constant.

Average Case Complexity

The expected number of steps taken by an algorithm for randomly chosen inputs of size n.

Machine-independent Analysis

A way to analyze algorithms in general terms, without reliance on specific hardware or implementation details.

Insertion Sort

A sorting algorithm that builds a sorted array one element at a time, with an average and worst-case complexity of O(n²).

Quicksort

A divide-and-conquer sorting algorithm that selects a pivot and partitions the array, with an average case complexity of O(n log n).

Selection Sort

A sorting algorithm that repeatedly selects the smallest element from the unsorted portion and moves it to the sorted portion, with a complexity of O(n²).

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, with a complexity of O(n²).

Logarithmic Growth

A situation where the performance of an algorithm increases logarithmically as the input size increases, represented as O(log n).

Constant Time Operation

An operation that takes the same amount of time to complete, regardless of the input size, represented as O(1).

Exponential Growth

A situation where the running time of an algorithm doubles with each additional element in the input size; expressed as O(2^n).