0 - Introduction

note: this is not an exact, formal definition
A computational problem $P$ is a relation $P\subset I\times O$ from an Input space $I$ to an output space $O$, such that the input output pair $io\in P$ only if $o$ is the correct output for $i$.

We often specify a problem by a predicate $P$ where $o$ is the correct output for $i$ if $P(i,o)$ is true.

Given an Input output space $I,O$ and a problem $P$, an algorithm is a function $f:I\to O$. The algorithm $f$ solves the problem $P$: if $P(i,f(i))$ is true for each $i\in I$.

Let $\mathbb{H}$ be a family of functions from $S\to \mathbb{R}$. for $f,g\in \mathbb{H}$, $f=O(g)$ if for each $s\in S$, $f(s)\le Cg(s)$ for some $C>0$.
$f=\mathrm{\Omega }(g)$ if $g=O(f)$.
$f=\mathrm{\Theta }(g)$ if $f=O(g)$ and $g=O(f)$.
Moreover, the family of functions $\{f:f(s)\le Cg(s)\}$ is the class of all functions that are $O(g)$. In such cases, we write $f\in O(g)$.

In general, a model of computation, is a collection of operations that a computer can preform in $O(1)$ time. Along with models of memory and so on. (this is oversimplified)
A word is block of $w$ bits.
Memory is an addressable contiguous sequence of words. each word in memory, is also addressable by some word.
A processor, is an abstract entity that supports many constant time operations on a block of $O(1)$ words:

• Given a word $a$, it can read the word at address $a$. it can write a word to the address $a$.
• It's important that every word in the memory is addressable by some word. Suppose our memory is a sequence of $n$ words. then, we can simply address it as $1,2,\dots ,n$. But each of these numbers must be in binary, hence, we would need $lo{g}_2(n)$ bits to address every word-block in memory, which means that our word size must grow at least as fast as $lo{g}_2(n)$, that is $w=\mathrm{\Omega }(\log (n))$.
• It can also perform integer and bitwise arithmetic, as well as logical operations.

An interface is a collection of objects $A$, and a collection of operations $Op(A)$. A data structure, is a way to store the objects $A$, and a collection of algorithms, which supports each operation in $Op(A)$.