2.13. Glossary

algorithm

a generic, step-by-step list of instructions for solving a problem

average case

refers to when an algorithm performs between its worst and best case given a certain data set or circumstance

best case

refers to when an algorithm performs especially good given a certain data set or circumstance

Big-O notation

another term for order of magnitude; written as \(O(f(n))\)

brute force

technique that tries to exhaust all possibilities of a problem

contiguous

adjacent or next to

dynamic size

able to change size automatically

exponential

function represented as a number being raised to a power that increases like \(f(n)= 2^{n}\)

hash table

a collection consisting of key-value pairs with an associated hash function that maps the key to the associated value.

linear

function that grows in a one to one relationship with its input like \(f(n) = n\)

logarithmic

functions that are the inverse of exponential functions usually presented as \(f(n) = logn\)

order of magnitude

function describing the part \(T(n)\) that increases the fastest as the value of n increases (a function describing an algorithm’s steps as the size of the problem increases).

quadratic

function describing a relationship who’s highest order is a number squared

simplified: \(f(n) = x^{2}\)

complex: \(ax^{2} + bx + c\)

worst case

refers to when an algorithm performs especially poorly given a certain data set or circumstance

vector

sequence container storing data of a single type that is stored in a dynamically allocated array which can change in size.

2.14. Matching

    Q-1: Drag the word on the left to its corresponding definition Review classes and their properties
  • algorithm
  • Step-by-step list of instructions for solving a problem.
  • dynamic size
  • Able to change size automatically
  • exponential
  • Function represented as a number being raised to a power that increases.
  • hash table
  • A collection consisting of key-value pairs with an associated hash function that maps the key to the associated value.
  • linear
  • Function that grows in a one to one relationship with its input.
  • logarithmic
  • functions that are the inverse of exponential functions
  • order of magnitude
  • a function describing an algorithm's steps as the size of the problem increases.
  • average case
  • When an algorithm performs between its worst and best case given a certain data set or circumstance.
  • vector
  • Sequence container storing data of a single type in a dynamically allocated array.
  • worst case
  • When an algorithm performs especially poorly given a certain data set or circumstance.
  • quadratic
  • Function describing a relationship who's highest order is a number squared
  • best case
  • When an algorithm performs especially good given a certain data set or circumstance
  • Big-O notation
  • another term for order of magnitude
  • brute force
  • Technique that tries to exhaust all possibilities of a problem
  • contiguous
  • Adjacent
You have attempted of activities on this page
Next Section - 3. Linear Structures