Time Complexity (Big O)

DSA · Introduction to DSA

Theory

Time complexity describes how the number of steps an algorithm performs grows as the input size n grows. Big O notation keeps only the dominant term and drops constants: an algorithm doing 3n + 5 steps is O(n). Common classes from fastest to slowest are O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic and O(2ⁿ) exponential. Big O usually describes the worst case, while best and average cases are stated separately when they differ.

Why we use it

Big O lets you compare algorithms without running them on every machine. An O(n²) solution that is fine for 1,000 items may take hours for 1,000,000, while an O(n log n) one finishes in seconds.

When to use it

Use it to choose between approaches, to explain your solution in interviews, and to predict whether code will scale before it reaches production.

How it works

  1. Start with the algorithm
  2. Find the basic operation (comparison, assignment)
  3. Count how many times it runs for input size n
  4. Are there nested loops over n? Yes: Multiply: O(n^2), O(n^3).... No: Add sequential parts: O(n) + O(n) = O(n).
  5. Drop constants and lower-order terms
  6. Report the dominant term, e.g. O(n log n)

Syntax

O(1)        index into an array, dict lookup
O(log n)    binary search, balanced tree lookup
O(n)        single loop over the data
O(n log n)  merge sort, quick sort (average)
O(n²)       nested loops over the same data
O(2ⁿ)       trying every subset

Rule: keep the biggest term, drop constants
  3n² + 10n + 7  ->  O(n²)

Example

def count_steps(n):
    linear = 0
    for i in range(n):
        linear += 1
    quadratic = 0
    for i in range(n):
        for j in range(n):
            quadratic += 1
    return linear, quadratic

for n in [10, 100, 1000]:
    lin, quad = count_steps(n)
    print("n =", n, "| O(n) steps:", lin, "| O(n^2) steps:", quad)

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic