NotesAtHKU

We usually determine the efficiency of an algorithm by analyzing its time and space complexity.

Size of input

An input is a data structure that is given to an algorithm to solve a problem. The size of an input is the number $\mathbf{n}$ of elements in the input.

How do we assess time complexity?

When we analyize time complexity, we are interested in the efficiency of an algorithm as a function of the size of the input.

As different machines have varying speeds of processors, time is not a good fit for measuring algorithm efficiency.

We can consider the number of operations an algorithm performs relative to the size of the input, which will isolate the algorithm from the performing machines.

However, different operations have varying efficiencies, so instead we consider the growth rate of the total number of operations as a function of the input size. The analysis of such is called Asymptotic analysis.

Time complexity

The rate of growth of the total number of operations an algorithm performs relative to size of input.

Space complexity

The rate of growth of the total amount of memory an algorithm uses relative to size of input.

Asymptotic notation

Growth rate / Complexity: The basis of asymptotic notations

We are defining a certain function $\mathbf{T(n)}$ to represent the total number of operations with respect to $\mathbf{n}$ (the size of the input).

When we say $T(n)$ is $A$ of $(g(n))$ (or $T(n)\in A(g(n))$ ), we are saying that the growth rate of $T(n)$ is bounded by $A(g(n))$ under a specific mathematical inequality defined by $A$ .

General definition of asymptotic notations

T(n) \in A(g(n))\ \text{iff}\ \exists\ c > 0:

T(n) \simeq c\cdot g(n)\ \forall\ n \geq n_0 > 0

T(n) \in a(g(n))\ \text{if}\ \forall\ c > 0\ \exists\ n_0 \geq 0:

T(n) \sim c\cdot g(n)\ \forall\ n \geq n_0

Note that the $\in$ is interchangable with $=$ . The meaning does not really matter.

To prove non-strict boundaries, we need to show the existence of constants $c, n_0$ that satisfies the inequality.

Prove ex. 1 Prove ex. 2 Prove ex. 3

Definition of all asymptotic notations

Notation	Condition	Asymptotic boundary	Name
$O(g)$	$T(n) \htmlClass{text-red-500}{\leq} c\cdot g(n)$	Upper	Big O
$\Omega(g)$	$T(n) \htmlClass{text-red-500}{\geq} c\cdot g(n)$	Lower	Big Omega
$\Theta(g)$	$c_1\cdot g(n)\htmlClass{text-red-500}{\leq} T(n) \htmlClass{text-red-500}{\leq} c_2\cdot g(n)$	Tight	Big Theta / Order of growth
$o(g)$	$T(n) \htmlClass{text-red-500}{<} c\cdot g(n)$	Strictly upper	Little o
$\omega(g)$	$T(n) \htmlClass{text-red-500}{>} c\cdot g(n)$	Strictly lower	Little omega

Growth rate functions

We use the likeness of $g(n)$ to describe the complexity of $T(n)$ . The following gives the common growth rate functions (increasing order of growth):

1 < \log n < \sqrt{n} < n < n\log n < n^2 < n^3 < 2^n < n! < n^n

Note that the higher the growth rate, the more complex the algorithm.

Note the following growth rate equivilencies:

$\log(n!)=\Theta(n\log(n))$ (prove not needed, related to lower bound of sorting algorithms)
$\Theta(\log_2n)=\Theta(\log_{10}n)$ as $\log_2n = \frac{\log n}{\log 2} = c\times\log n$

Identifying asymptotic growths

Non-strict: Identify the term with the highest growth rate in $T(n)$ would be $g(n)$ .

Strict: Choose the next / previous growth rate function with reference to the list depending on if it's upper / lower.

You can use the same logic to determine if some $f(n)$ is $A/a$ of $g(n)$ .

Note that as the defintions are specified by an inequality, there could be multiple satisfying $g(n)$ for the same $T(n)$ and all of them are valid. However, keep in mind the only useful $g(n)$ for analysis would be closest to the condition boundary.

If the function functuates, there is not a consistent growth rate unless a boundary is specified.

Example

Big Theta of resursive relations

When tasked to find find the asymptotic notation of a recursive relation, we are required to give the Big Theta notation of the relation.

The straight forward way is to find the closed-form expression and identify the growth rate. However, this is not always possible.

Useful growth rates

Sum of square series: $\sum_{i=1}^{k}f(n, i)^2\in \Theta(n^3)$
Sum of series: $\sum_{i=1}^{k}f(n, i)\in \Theta(n^2)$

Time complexity of code

Operation of time complexities

By definition:

O(g)+O(g)=k\times O(g)=O(g)

O(g)\times O(g)=O(g\times g)

O(g_1)+O(g_2)=O(g_2),\quad g_2 > g_1\text{ in terms of order of growth}

Our goal is to examine how the runtime grows with respect to the input size. Consider the following example:

# 1
for num in arr:         # n
if num > max_val:       # n
max_val = num           # n
return max_val          # 1

It should be acknowledged that each operation / line would take different amounts of time to compute. However, as we are interested in the runtime $T(n)$ 's growth rate, we can treat all operations to take $1$ unit of time.

Hence, $T(n)=O(1)+O(1)+O(1)+O(1)+O(n)+O(n)+O(n)+O(1)=O(n)$

Typical growth rates and common occurance

Growth	Occurrence
$1$	Statements that run a set number of times with no respect to the input size
$\log n$	Algorithms that solve a big problem by transformation into a series of smaller problems, cutting the problem size by some constant fraction at each step.
$n$	"for" loops that have $n$ amount of iterations per program run
$n\log n$	Algorithms that solve a problem by breaking it up into smaller sub-problems, solving them independently, and then combining the solutions.
$n^k$	Nested "for" loops that have $n$ amount of iterations per program run

Algorithm Analysis