Time Complexity

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Analysis of Algorithms #◇Data Structures #◇Time Complexity #◇Space Complexity

---

◇Overview

Time complexity measures the amount of computational time an algorithm takes as a function of the input size $n$.

◇Key Concepts

Time complexity as a function $T(n)$ Counting primitive operations via ◇Frequency Count Asymptotic notation to classify growth rate Best-case, worst-case, and average-case time

◇Details / Theory

Definition

Time complexity is the computational complexity that describes the amount of time it takes to run an algorithm as a function of the length of the input. It is typically expressed using ◇Asymptotic Notation, most commonly ◇Big-O Notation.

How Time Complexity is Determined

1. Identify the input size $n$ (e.g., array length, number of nodes).
2. Count primitive operations as a function of $n$ using the ◇Frequency Count method.
3. Express the total count as a mathematical function $T(n)$.
4. Simplify using asymptotic notation — drop constants and lower-order terms.

Common Time Complexities (Ordered by Growth)

Relationship to Analysis Types

◇Worst-Case Analysis: $T(n) =$ maximum time over all inputs of size $n$ ◇Average-Case Analysis: $T(n) =$ expected time over all inputs of size $n$ ◇Best-Case Analysis: $T(n) =$ minimum time over all inputs of size $n$

Measuring Time Complexity

We do not measure actual wall-clock time (that depends on hardware, language, etc.). Instead, we count the number of primitive/elementary operations executed. This is done via ◇A Priori Analysis using the ◇RAM Model.

◇Common Pitfalls

Confusing time complexity with actual execution time — $O(n^2)$ doesn't mean "slow," it describes the growth rate. Forgetting that Big-O drops constants: $O(2n)$ is just $O(n)$. Ignoring the difference between best, worst, and average case.

◇Summary

TL;DR — Time complexity measures how an algorithm's running time scales with input size $n$, expressed using asymptotic notation (commonly Big-O). It is determined by counting primitive operations via frequency count analysis.

◇Links

Related: ◇Running Time — ◇Space Complexity — ◇Frequency Count — ◇Asymptotic Notation — ◇Big-O Notation — ◇Growth Rates — ◇Worst-Case Analysis — ◇Average-Case Analysis — ◇Best-Case Analysis Source / Reference: Handout 01, Handout 02

◇References & Navigation

• Previous Topic: ◇Substitution Method
• Next Topic: ◇Worst-Case Analysis
• Related Notes: ◇Space Complexity, ◇Running Time