Analysis of an Algorithm, Asymptotic Notations and Time-Space Trade-off

1. Analysis of an Algorithm

An algorithm is a finite sequence of well-defined steps used to solve a particular problem.

Algorithm analysis is the process of evaluating an algorithm with respect to the resources required for its execution, mainly:

1. Time – How much computational time the algorithm requires.

2. Space – How much memory the algorithm requires.

The purpose of algorithm analysis is to determine whether an algorithm is efficient and to compare different algorithms for solving the same problem.

Example

Suppose we want to find an element in an array of n elements.

Linear Search examines elements one by one.

int search(int a[], int n, int key)
{
    for (int i = 0; i < n; i++)
    {
        if (a[i] == key)
            return i;
    }

    return -1;
}

If the required element is at the last position, approximately n comparisons may be required.

Therefore, the running time increases with the size of the input.

---

2. Why Do We Analyze Algorithms?

Two algorithms may produce the same output but require different amounts of time and memory.

For example, consider two algorithms with running times:

$$T_1(n)=n$$

and

$$T_2(n)=n^2$$

For small values of n, the difference may not be significant. However, as n becomes large, the second algorithm becomes considerably slower.

Therefore, algorithm analysis helps us:

• Select an efficient algorithm.

• Compare alternative algorithms.

• Predict performance for large inputs.

• Identify inefficient portions of a program.

• Estimate resource requirements.

• Design scalable software.

---

3. Factors Affecting Algorithm Performance

The performance of an algorithm can depend on several factors:

3.1 Input Size

The amount of input data is represented generally by n.

For example:

• Number of elements in an array = n

• Number of vertices in a graph = V

• Number of edges in a graph = E

As input size increases, execution time may increase.

3.2 Input Characteristics

The arrangement of input data can affect execution time.

For example, in linear search:

Array = [10, 20, 30, 40, 50]

Searching for 10 requires only one comparison, whereas searching for 50 requires five comparisons.

3.3 Hardware and Software Environment

Actual execution time also depends on:

• Processor speed

• Memory

• Compiler

• Operating system

• Programming language implementation

For theoretical algorithm analysis, we generally avoid depending on these machine-specific factors.

---

4. Types of Algorithm Analysis

Algorithm performance is commonly considered under three cases.

4.1 Best Case

The best case represents the minimum amount of work performed by an algorithm for an input of size n.

Example: Linear Search

If the required element is the first element:

[25, 40, 55, 70, 85]
 ↑
 key

Only one comparison is required.

Therefore:

$$T_{best}(n)=O(1)$$

---

4.2 Worst Case

The worst case represents the maximum amount of work performed by an algorithm for an input of size n.

For linear search, the key may be:

• at the last position, or

• absent from the array.

Approximately n elements may need to be examined.

Therefore:

$$T_{worst}(n)=O(n)$$

---

4.3 Average Case

The average case represents the expected amount of work over possible inputs.

For linear search, if the element is equally likely to occur at any position, the average number of comparisons is approximately:

$$\frac{n+1}{2}$$

Although this is approximately n/2, its asymptotic complexity is:

$$O(n)$$

---

5. Time Complexity

Time complexity describes how the running time of an algorithm grows as the input size increases.

It does not necessarily mean the exact time in seconds.

Instead, it describes the growth rate of the number of fundamental operations.

For example:

for (int i = 0; i < n; i++)
{
    printf("%d ", i);
}

The loop executes n times.

Therefore:

$$T(n)=O(n)$$

---

6. Counting Basic Operations

One way to analyze an algorithm is to count the number of important operations it performs.

Consider:

for (int i = 0; i < n; i++)
{
    sum = sum + a[i];
}

The addition operation occurs n times.

Thus, the running time grows linearly with n.

$$T(n) \propto n$$

Hence:

$$T(n)=O(n)$$

The objective is generally to determine the order of growth, rather than calculate every machine-level instruction.

---

7. Common Time Complexities

The most commonly encountered complexity classes are:

Complexity	Name	Example
O(1)	Constant	Accessing a[5]
O(log n)	Logarithmic	Binary Search
O(n)	Linear	Linear Search
O(n log n)	Linearithmic	Merge Sort
O(n²)	Quadratic	Bubble Sort
O(n³)	Cubic	Some matrix algorithms
O(2ⁿ)	Exponential	Some recursive algorithms
O(n!)	Factorial	Some brute-force permutation algorithms

As n becomes very large, algorithms with slower-growing complexity generally become more desirable.

---

8. Asymptotic Analysis

Asymptotic analysis is a mathematical technique used to describe the growth of an algorithm's resource requirements as the input size approaches a large value.

It allows us to ignore:

• Machine-dependent execution time

• Constant factors

• Lower-order terms

and focus on the dominant growth term.

Example

Suppose:

$$T(n)=3n^2+5n+10$$

For large n, the n² term dominates the other terms.

Therefore:

$$T(n)=O(n^2)$$

The constants and lower-order terms are ignored when expressing asymptotic growth.

---

9. Asymptotic Notations

The three fundamental asymptotic notations are:

1. Big-O notation — O

2. Big-Omega notation — Ω

3. Big-Theta notation — Θ

They provide mathematical bounds on the growth of an algorithm.

---

10. Big-O Notation — O()

Big-O notation provides an asymptotic upper bound on the growth of a function.

It is commonly used to express the worst-case growth of an algorithm.

If an algorithm takes:

$$T(n)=4n^2+3n+7$$

then:

$$T(n)=O(n^2)$$

because n² is the dominant term.

Formal Definition

A function f(n) is:

$$O(g(n))$$

if there exist positive constants c and n₀ such that:

$$0 \leq f(n) \leq c\,g(n)$$

for all:

$$n\geq n_0$$

Example

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

Since the dominant term is n:

$$f(n)=O(n)$$

---

11. Big-Omega Notation — Ω()

Big-Omega notation provides an asymptotic lower bound.

If:

$$f(n)=\Omega(g(n))$$

then f(n) grows at least as fast as g(n) asymptotically.

Formal Definition

There exist positive constants c and n₀ such that:

$$0 \leq c\,g(n)\leq f(n)$$

for all:

$$n\geq n_0$$

Example

For:

$$f(n)=3n^2+2n+1$$

we can say:

$$f(n)=\Omega(n^2)$$

---

12. Big-Theta Notation — Θ()

Big-Theta notation provides a tight asymptotic bound.

It means that the function grows at the same asymptotic rate as the given function.

If:

$$f(n)=\Theta(g(n))$$

then both an upper and lower bound of the same order exist.

Example

Consider:

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

The dominant term is n².

Therefore:

$$f(n)=\Theta(n^2)$$

It is also true that:

$$f(n)=O(n^2)$$

and

$$f(n)=\Omega(n^2)$$

---

13. Comparison of O, Ω and Θ

Notation	Meaning	Type of Bound
O(g(n))	At most this order of growth	Upper bound
Ω(g(n))	At least this order of growth	Lower bound
Θ(g(n))	Exactly this order asymptotically	Tight bound

Easy way to remember

O → Upper bound

Ω → Lower bound

Θ → Tight bound

---

14. Simplifying Asymptotic Expressions

Consider:

$$T(n)=5n^3+7n^2+20n+100$$

Step 1: Identify the highest-order term.

$$n^3$$

Step 2: Ignore constant coefficient.

$$5n^3 \rightarrow n^3$$

Step 3: Ignore lower-order terms.

Therefore:

$$T(n)=\Theta(n^3)$$

Similarly:

$$7n^2+4n+8=\Theta(n^2)$$

and

$$10n+50=\Theta(n)$$

---

15. Analysis of Simple C Programs

Example 1: Constant Complexity

int x = a[0];

Only one array element is accessed.

Therefore:

$$T(n)=O(1)$$

---

Example 2: Linear Complexity

for (int i = 0; i < n; i++)
{
    printf("%d ", a[i]);
}

The loop executes n times.

Therefore:

$$T(n)=O(n)$$

---

Example 3: Quadratic Complexity

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        printf("%d ", a[i][j]);
    }
}

The outer loop executes n times.

For each outer-loop iteration, the inner loop executes n times.

Therefore:

$$T(n)=n\times n=n^2$$

Hence:

$$T(n)=O(n^2)$$

---

Example 4: Logarithmic Complexity

In binary search, the search space is approximately divided into half after every comparison.

The sequence is:

$$n,\frac n2,\frac n4,\frac n8,\ldots,1$$

After k divisions:

$$\frac{n}{2^k}=1$$

Therefore:

$$2^k=n$$

Taking logarithm:

$$k=\log_2n$$

Hence binary search has:

$$T(n)=O(\log n)$$

---

16. Space Complexity

Space complexity describes the amount of memory required by an algorithm as a function of input size.

It includes memory required for:

• Input data

• Variables

• Auxiliary data structures

• Temporary storage

• Function-call stack

• Recursion

For example:

int sum = 0;

for (int i = 0; i < n; i++)
{
    sum += a[i];
}

Apart from the input array, only a few additional variables are used.

Therefore, the auxiliary space is:

$$O(1)$$

---

17. Auxiliary Space

Auxiliary space refers to the extra memory used by an algorithm apart from the memory required to store the input.

For example, if an algorithm uses an additional array of size n:

$$Auxiliary\ Space=O(n)$$

If it uses only a few variables:

$$Auxiliary\ Space=O(1)$$

This distinction is important when analyzing memory-efficient algorithms.

---

18. Time-Space Trade-off

A time-space trade-off occurs when an algorithm uses more memory to reduce execution time, or uses less memory at the cost of increased execution time.

In other words:

We may sacrifice memory to gain speed, or sacrifice speed to save memory.

---

19. Example of Time-Space Trade-off

Suppose we frequently need to search for values in a large collection.

Approach 1: Search Every Time

Store the data in an array and perform linear search whenever required.

• Extra memory: low

• Search time: O(n)

Approach 2: Use Additional Storage

Create an appropriate indexing or hashing structure.

• Additional memory: higher

• Search time: potentially much lower, often approximately O(1) average for a well-designed hash table

Thus, additional memory can be used to reduce computation time.

---

20. Example: Fibonacci Numbers

Consider the recursive Fibonacci implementation:

int fib(int n)
{
    if (n <= 1)
        return n;

    return fib(n - 1) + fib(n - 2);
}

This approach repeatedly calculates the same values.

Its time complexity is exponential:

$$O(2^n)$$

However, we can store previously calculated Fibonacci values.

fib[0] = 0;
fib[1] = 1;

for (int i = 2; i <= n; i++)
{
    fib[i] = fib[i - 1] + fib[i - 2];
}

Now:

$$Time = O(n)$$

but:

$$Space = O(n)$$

Thus, additional memory is used to significantly reduce computation time.

This technique is called memoization when previously computed results are stored for reuse.

---

21. Common Examples of Time-Space Trade-off

Technique	More Space	Benefit
Hash Table	Yes	Faster searching
Memoization	Yes	Avoids repeated computation
Dynamic Programming	Often yes	Reduces repeated subproblems
Caching	Yes	Faster access to frequently used data
Indexing	Yes	Faster data retrieval
Lookup Tables	Yes	Faster computation

The appropriate trade-off depends on the application.

For example, in a memory-constrained embedded system, saving memory may be more important than achieving the minimum possible execution time. In a high-performance server, faster response may justify additional memory.

---

22. Time-Space Trade-off vs Space-Time Complexity

These terms should not be confused.

Space Complexity

Measures how much memory an algorithm requires.

Time Complexity

Measures how the execution work grows with input size.

Time-Space Trade-off

Describes the design decision in which one resource is increased to reduce the other.

For example:

$$More\ Space \rightarrow Less\ Time$$

or

$$Less\ Space \rightarrow More\ Time$$

This is not an absolute rule for every algorithm, but it is a common design principle.

---

23. Important Complexity Classes

From generally more scalable to less scalable for large n:

$$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$

This ordering describes the growth rate, not exact execution time for every possible input.

---

24. Summary

Algorithm analysis is essential for evaluating the efficiency of algorithms. The two primary resources considered are time and space.

Time complexity measures how the computational work grows with input size, while space complexity measures memory requirements.

Asymptotic notations provide mathematical ways of describing algorithm growth:

• Big-O (O) → upper bound

• Big-Omega (Ω) → lower bound

• Big-Theta (Θ) → tight bound

The time-space trade-off occurs when additional memory is used to reduce computation time or when memory is conserved at the cost of additional computation.

These concepts form the mathematical foundation for comparing and selecting algorithms throughout the study of Data Structures and Algorithms.