Growth of Functions, Asymptotic Analysis, and Complexity Classes (P, NP, NP-Complete, NP-Hard)

Introduction

These lectures focus on mathematical foundations of algorithm analysis. You’ll learn how functions grow, how to measure algorithm efficiency using asymptotic notations, and how problems are classified into complexity classes such as P, NP, NP-Complete, and NP-Hard. These concepts form the basis of theoretical computer science and practical applications like cryptography, AI, and optimization.

Algorithm Analysis and Complexity

Growth of Functions
- Examples of Function Growth
- Rate of Growth

Asymptotic Analysis
- Big-O Notation (O)
- Big-Theta Notation (Θ)
- Big-Omega Notation (Ω)
- Small-o and Small-ω Notations
- Properties of Asymptotic Notation

Basic Efficiency Classes
Special Complexity Classes
- Class P
- Class NP
- NP-Complete Problems
- NP-Hard Problems

Applications of Complexity Theory
Conclusion

Algorithm Analysis and Complexity

Analysis of algorithms = determining time and space required for execution.

Importance: Predicts algorithm behavior without implementation.
Two approaches:
- Experimental Studies (Naïve): Run code and measure time.
- Theoretical Analysis: Use mathematical models and asymptotic notation.

Growth of Functions

The growth of a function indicates how fast execution time increases with input size.

Examples of Function Growth

$f_1(n) = 100n + 1$ $f_{1} (n) = 100 n + 1$ vs

$f_2(n) = n^2 + n + 1$ $f_{2} (n) = n^{2} + n + 1$ → For small

$n$ $n$ , linear looks worse; for large

$n$ $n$ , quadratic dominates.

$f_3(n) = n + 1,000,000$ $f_{3} (n) = n + 1, 000, 000$ vs

$f_2(n) = n^2 + n + 1$ $f_{2} (n) = n^{2} + n + 1$ → For large

$n$ $n$ , quadratic grows faster than linear.

Rate of Growth

Focus on how execution time grows rather than exact step counts.

Concern is with asymptotic behavior for large

$n$ $n$ .

Asymptotic Analysis

Used to analyze algorithms as input size grows.

Big-O Notation (O)

Upper bound (worst case).

Example:

$f(n) = n^2 + n = O(n^2)$ $f (n) = n^{2} + n = O (n^{2})$ .

Big-Theta Notation (Θ)

Tight bound (average case or exact growth).
Example:

$f(n) = 3n^5 + n^4 = Θ(n^5)$ $f (n) = 3 n^{5} + n^{4} = Θ (n^{5})$ .

Big-Omega Notation (Ω)

Lower bound (best case).

Small-o and Small-ω Notations

Define stricter growth relations compared to Big-O and Big-Ω.

Properties of Asymptotic Notation

Transitivity: If

$f = Θ(g)$ $f = Θ (g)$ and

$g = Θ(h)$ $g = Θ (h)$ , then

$f = Θ(h)$ $f = Θ (h)$ .
Symmetry:

$f = Θ(g)$ $f = Θ (g)$ iff

$g = Θ(f)$ $g = Θ (f)$ .

Complementarity:

$f = O(g)$ $f = O (g)$ iff

$g = Ω(f)$ $g = Ω (f)$ .

Basic Efficiency Classes

Algorithms typically fall into these efficiency classes:

O(1): Constant time
O(log n): Logarithmic

O(n): Linear
O(n log n): Linearithmic (e.g., Merge Sort)
O(n²): Quadratic

O(n³): Cubic
O(2ⁿ): Exponential
O(n!): Factorial

Special Complexity Classes

Class P

Problems solvable in polynomial time (efficient).
Examples: Sorting (O(n log n)), Shortest Path (O(n²)).

Class NP

Problems whose solutions can be verified in polynomial time.

Example: Sudoku solution checking.

NP-Complete Problems

Hardest problems in NP.
If one NP-Complete problem is solved in polynomial time, all NP problems can be solved efficiently.

Example: Traveling Salesman Problem (decision version).

NP-Hard Problems

At least as hard as NP-Complete; may not be verifiable in polynomial time.
Example: Halting Problem (undecidable).

Applications of Complexity Theory

Cryptography: RSA depends on factorization (hard problem).
Databases: Query optimization is NP-hard.
AI & Machine Learning: Feature selection and planning problems.

Logistics: Vehicle routing and job scheduling.

Conclusion

Lectures 6–8 build the theoretical foundation of algorithm analysis. By understanding growth of functions, asymptotic notations, and complexity classes, students can evaluate algorithms beyond implementation details. The classification of problems into P, NP, NP-Complete, and NP-Hard explains why some problems remain unsolved and underpins critical applications in cryptography, optimization, and AI. lecture Lecture # 0678###