Evaluating algorithm complexity is one of the most fundamental skills in computer science and software engineering. It’s how we determine which algorithm is more efficient — both in execution speed and in memory usage.

1. Why Do We Evaluate Complexity?

Imagine you’ve solved a problem using two different algorithms. Both give correct results, but you want to know:

• Which one is faster?
• Which one uses less memory?
• Which will scale better with larger inputs?

To answer these questions, you must evaluate the complexity of each algorithm and compare them.

2. Two Sides of Complexity

1. Time Complexity
   • The amount of time an algorithm takes to complete.
   • Measured in steps, not seconds.
2. Space Complexity
   • The amount of memory an algorithm needs to run.

In this tutorial, we’ll focus on time complexity first.

3. Why We Don’t Measure in Seconds

If you run the same algorithm on different machines, you’ll get different times.
For example:

• Sorting 100,000 elements on a modern laptop: 0.001 seconds
• Sorting the same array on an old machine: 3 seconds

These differences come from:

• CPU speed
• RAM performance
• Storage latency
• Other hardware factors

This makes seconds a bad universal unit for comparison.

4. The Step-Based Approach

Instead of seconds, we measure algorithm execution in indivisible processor operations (often called steps).

Why?

• A processor step is a constant-duration action.
• It’s hardware-independent in our analysis model.
• It allows us to compare algorithms without caring about the specific machine.

This step-based model is the foundation of time complexity analysis.

Formal Definition

Let:

• n = size of input data
• T(n) = number of steps the algorithm takes

Then:

Time Complexity is a function T(n) that shows how the number of steps grows as the input size increases.

5. Indivisible Operations

When analyzing code, we treat certain programming language operations as one step each:

• Variable initialization (int x = 5;)
• Arithmetic operations (+, -, *, /)
• Logical operations (&&, ||)
• Comparisons (==, !=, <, >=)
• Returning a value from a function
• Printing to output (for simplicity in analysis)

Even though real hardware may take multiple low-level instructions to execute them, we approximate each as one step for complexity analysis.

6. Example 1 — Constant Complexity

int sum = 0;        // 1 operation
sum = sum + 5;      // 1 operation
sum = sum / 2;      // 1 operation
return sum;         // 1 operation

• Total = 1+1+1+1=41 + 1 + 1 + 1 = 41+1+1+1=4 steps
• T(n) = 4
• This algorithm does not depend on input size → O(1) (constant time)

7. Example 2 — A Loop with Operations

Let’s analyze:

int x = 0;                    // 1 operation
for (int i = 1; i <= n; i++)  // init: 1, compare: n, increment: n
{
    x++;                      // runs n times
}
return x;                     // 1 operation

Step-by-step:

1. int x = 0; → 1 step
2. int i = 1; → 1 step
3. i <= n; comparison → runs nnn times
4. i++ increment → runs nnn times
5. x++ → runs nnn times
6. return x; → 1 step

T(n) = 1 + 1 + n + n + n + 1
Simplified: T(n) = 3 + 3n

We drop constants when using Big O → O(n)

8. General Formula for Loop Complexity

For a loop like:

for (...) {
    // body
}

Loop Complexity Formula:

Steps=n×(operations inside the body)

If the loop has setup and increments:

• Add 1 for initialization
• Add n for comparisons
• Add n for increments

For complexity classes (O(n), O(n²), etc.), we focus on the dominant term.

9. Example 3 — Using the Formula

int x = 0;           // 1 step
for (int i = 0; i < n; i++) {  // init: 1, compare: n, increment: n
    x++;             // 1 step inside loop
}
return x;            // 1 step

• Loop body = 1 step
• Loop runs n times → n×1=n steps
• Total = 1 (x init) + 1 (i init) + n (compare) + n (increment) + n (x++) + 1 (return)
• T(n) = 3 + 3n → O(n)

10. Summary Rules for Time Complexity Evaluation

• Treat indivisible operations as 1 step each.
• Count total steps for the algorithm.
• For loops:
  • Single loop: O(n)
  • Nested loops: Multiply complexities → O(n²), O(n³), etc.
• Ignore constants and lower-order terms for Big O notation.