Standard Functions and Notations for Algorithm Analysis

Introduction

When analyzing algorithms, we frequently encounter different mathematical functions and notations. Understanding their properties and growth rates is essential for comparing the efficiency of algorithms.

The commonly used functions are

1. Monotonic Functions
2. Floor and Ceiling Functions
3. Modular Arithmetic
4. Polynomial Functions
5. Exponential Functions
6. Logarithmic Functions
7. Factorial Function
8. Functional Iteration
9. Iterated Logarithm
10. Fibonacci Numbers

---

1. Monotonic Functions

A function whose values always increase or always decrease is called a monotonic function.

Monotonically Increasing

If

$$m \le n$$

then

$$f(m)\le f(n)$$

Example

$$f(n)=n,\quad n^2,\quad \log n,\quad 2^n$$

---

Monotonically Decreasing

If

$$m\le n$$

then

$$f(m)\ge f(n)$$

Example

$$f(n)=\frac1n$$

---

Strictly Increasing

If

$$m<n$$

then

$$f(m)<f(n)$$

Example

$$f(n)=2n+5$$

---

Strictly Decreasing

If

$$m<n$$

then

$$f(m)>f(n)$$

Example

$$f(n)=\frac1n$$

---

2. Floor and Ceiling Functions

These functions are widely used in Divide-and-Conquer algorithms.

Floor Function

The floor of a real number is the greatest integer less than or equal to the number.

Notation

$$\lfloor x\rfloor$$

Example

x	Floor(x)
3.8	3
7.2	7
5	5
-2.3	-3

---

Ceiling Function

The ceiling of a number is the smallest integer greater than or equal to the number.

Notation

$$\lceil x\rceil$$

Example

x	Ceiling(x)
3.2	4
5.9	6
7	7
-2.3	-2

---

Important Properties

$$\lfloor n\rfloor=n$$
$$\lceil n\rceil=n$$

for every integer $n$.

Also,

$$x-1<\lfloor x\rfloor\le x\le\lceil x\rceil<x+1$$

---

3. Modular Arithmetic

The modulo operator gives the remainder after division.

Notation

$$a\bmod n$$

Formula

$$a\bmod n=a-n\left\lfloor\frac an\right\rfloor$$

---

Examples

Expression	Answer
17 mod 5	2
20 mod 4	0
35 mod 6	5

---

Applications

• Hash Tables
• Cryptography
• Circular Queues
• Cyclic Scheduling

---

4. Polynomial Functions

A polynomial is

$$a_0+a_1n+a_2n^2+\cdots+a_dn^d$$

where

• $a_i$ are constants
• $d$ is the degree.

---

Examples

$$3n^2+5n+1$$
$$7n^3+n^2+8$$

---

Important Result

Only the highest-degree term determines the asymptotic growth.

Example

$$3n^2+5n+8=\Theta(n^2)$$

---

5. Exponential Functions

General form

$$a^n$$

where

$$\mathrm{<br>}$$

Examples

$$2^n,\quad 3^n,\quad 10^n$$

---

Properties

$$a^0=1$$
$$a^ma^n=a^{m+n}$$
$$(a^m)^n=a^{mn}$$

---

Growth

Exponential functions grow much faster than polynomial functions.

Example

n	n²	2ⁿ
10	100	1024
20	400	1,048,576

---

6. Logarithmic Functions

Logarithms grow very slowly.

Common notations

$$\lg n=\log_2n$$
$$\ln n=\log_en$$
$$\log_{10}n$$

---

Important Rules

Product Rule

$$\log(ab)=\log a+\log b$$

Power Rule

$$\log(a^n)=n\log a$$

Change of Base

$$\log_ba=\frac{\log_ca}{\log_cb}$$

---

Examples

Expression	Answer
log₂8	3
log₂32	5
log₁₀100	2

---

Importance

Many efficient algorithms have

$$O(\log n)$$

time complexity.

Examples

• Binary Search
• AVL Trees
• Heap Operations

---

7. Factorial Function

Notation

$$n!$$

Definition

$$n!=1\times2\times3\times\cdots\times n$$

---

Examples

n	n!
0	1
1	1
3	6
5	120
6	720

---

Growth

Factorial grows faster than exponential functions.

Approximation (Stirling's Formula)

$$n!\approx\sqrt{2\pi n}\left(\frac ne\right)^n$$

Applications

• Counting permutations
• Backtracking algorithms
• Branch and Bound
• Combinatorics

---

8. Functional Iteration

Repeated application of the same function.

Notation

$$f^{(i)}(n)$$

Example

If

$$f(n)=2n$$

then

$$f^{(3)}(n)=8n$$

---

9. Iterated Logarithm

Notation

$$\log^*n$$

Read as

Log Star of n

It is the number of times logarithm must be applied until the result becomes less than or equal to 1.

Examples

n	log* n
2	1
4	2
16	3
65536	4

---

Importance

This is one of the slowest-growing functions in computer science.

It appears in

• Union-Find algorithms
• Disjoint Set Union (DSU)
• Some advanced graph algorithms

---

10. Fibonacci Numbers

Defined recursively as

$$F_0=0$$
$$F_1=1$$
$$F_n=F_{n-1}+F_{n-2}$$

---

Sequence

$$0,1,1,2,3,5,8,13,21,34,\ldots$$

---

Growth

Fibonacci numbers grow approximately as

$$\phi^n$$

where

$$\phi=\frac{1+\sqrt5}{2}\approx1.618$$

called the Golden Ratio.

---

Relative Growth of Common Functions

From slowest to fastest growth:

Growth Rate	Example
Constant	$1$
Logarithmic	$\mathrm{ \; log}n$
Polylogarithmic	$(\log n)^k$
Linear	$n$
Linearithmic	$n\log n$
Quadratic	$n^2$
Cubic	$n^3$
Polynomial	$n^k$
Exponential	$2^n$
Factorial	$n!$
$n^n$	$n^n$