Search

All pages, A to Z

• Asymptotic notation

  The notations O, Ω and Θ compare the growth of two functions for large inputs and ignore constant factors.

  intro
• Binary search

  Find a key in a sorted array. Compare the key with the middle item, and keep only the half that can hold the key.

  Θ(log n) worst · average10 languagesvisualintro
• Comparison model

  A model where an algorithm learns about its input only by comparing two items. The cost is the number of comparisons.

  intro
• Insertion sort

  Sort an array one item at a time. Take the next item and move it left until the item before it is not larger.

  Θ(n²) worst · average10 languagesvisualintro
• Loop invariant

  A statement about the variables of a loop that is true before each step. It is the main tool to prove that a loop is correct.

  intro
• Merge sort

  Sort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array.

  Θ(n log n) worst · average · best10 languagesvisualintro
• Search in a sorted array

  Given a sorted array and a key, find an index of the key, or report that the key is not in the array.

  Ω(log n) worstintro
• Sorting

  Put the items of a sequence in non-decreasing order by a key.

  Ω(n log n) worstintro