1/18
Flashcards for reviewing algorithm analysis concepts.
Algorithm
A procedure for accomplishing some tasks which, given an initial state, terminate in a defined end-state.
Space complexity
The amount of memory required by an algorithm to run to completion.
Time complexity
The amount of time it takes for an algorithm to run.
Fixed Part (Space Complexity)
The size required to store certain data/variables, that is independent of the size of the problem.
Variable Part (Space Complexity)
Space needed by variables, whose size is dependent on the size of the problem.
Define 'a' (Estimating Running Time)
The time taken by the fastest primitive operation.
Define 'b' (Estimating Running Time)
The time taken by the slowest primitive operation.
Pseudocode
High-level description of an algorithm; more structured than plain English, less detailed than a program.
Primitive Operations
Basic computations performed by an algorithm, largely independent from the programming language.
Big-Oh Notation
A notation that simplifies analysis by removing unneeded information, defining the upper bound of a function's growth rate.
Big Omega
Asymptotic lower bound.
Big Theta
Asymptotic tight bound.
ADT (Abstract Data Type)
A logical view of the data objects together with specifications of the operations required to create and manipulate them.
Representation(Data Type)
A specific encoding of an instance.
Opaque data types
data types in which the representation is not known to the user.
Transparent data types
data types in which the representation is profitably known to the user.