How to Calculate Time Complexity

What Is Time Complexity?

Time complexity describes how the running time of an algorithm changes when the input size grows.

It does not measure the exact time in seconds. Instead, it shows how efficiently an algorithm works.

For example, an algorithm may take: 

•  1 step for 1 item. 
•  10 steps for 10 items. 
•  1,000 steps for 1,000 items. 

This algorithm grows in a direct way. Its time complexity is called O(n). Here, 𝑛 represents the size of the input.

What is Big O Notation?

Big O notation is used to describe time complexity.

It focuses on the general growth of an algorithm and ignores small details, such as:

• The computer’s speed. 
• Small constants. 
• Minor operations. 
• Exact execution time.

Some common time complexities are:

Complexity	Name	Example
O(1)	Constant Time	Accessing an array item
O(log ⁡n)	Logarithmic Time	Binary search
O(n)	Linear Time	Reading every item in a list
O(n log⁡ n)	Linearithmic Time	Efficient sorting
O(n2)	Quadratic Time	Comparing every pair of items
O(2n)	Exponential Time	Some recursive problems
O(n!)	Factorial Time	Trying every possible arrangement

The lower the growth rate, the better the algorithm usually performs for large inputs.

Why Is Time Complexity Important?

Time complexity helps you compare algorithms before writing or running them.

Suppose you need to search for a name in a list. You could check every name one by one, or you could use a faster search method if the list is sorted.

Understanding time complexity helps you: 

•  Choose better algorithms. 
•  Write faster programs. 
•  Handle large amounts of data. 
•  Find slow parts of your code. 
•  Prepare for coding interviews.

How to Calculate Time Complexity

Use these simple steps to calculate the time complexity of an algorithm.

1. Step 1: Identify the Input Size

Find the value that represents the input size.

Usually, this value is called 𝑛.

For example:

def print_items(items):
	for item in items:
		print(item)

The input size is the number of items in the list. We call it 𝑛.

2. Step 2: Count the Main Operation

Find the operation that is repeated the most.

In the example above, print(item) runs once for every item.

If the list contains 𝑛 items, the operation runs 𝑛 times.

Therefore, the time complexity is:

𝑂(𝑛)
3. Step 3: Check Loops

A single loop that runs 𝑛 times usually has a time complexity of 𝑂(𝑛).

Example:

for i in range(n):
  print(i)

The loops runs 𝑛 times, so: Time complexity: O(n)

4. Step 4: Check Nested Loops
The outer loop runs 𝑛 times. For each outer-loop cycle, the inner loop also runs times. The total number of operations is: 𝑛 x 𝑛 = 𝑛² so, the time complexity is : O(n²)

Nested loops usually multiply their time complexities.

Example:

for i in range (n):
for j in range (n):
print (i, j)

5. Step 5: Check Separate Loops

Separate loops are usually added together.

For example:

for i in range(n):
									print(i) 
                                 for j in range(n):
                                 print(j)

The first loop takes 𝑂(𝑛).

The second loop also takes 𝑂(𝑛).

Together: 𝑂(𝑛)+𝑂(𝑛)=𝑂(2𝑛)

In Big O notation, constants are removed: 𝑂(2𝑛)=𝑂(𝑛)

Therefore, the final time complexity is: O(n)

6. Step 6: Remove Constants

Example:

(5𝑛)=𝑂(𝑛)

And

𝑂(3𝑛2+2𝑛+10)=𝑂(𝑛)

We keep only the fastest-growing term.

Common Time Complexity Examples

O(1): Constant Time

An operation takes the same amount of time regardless of the input size.

def get_first_item(items):
return items[0]

The function gets one item. It does not need to check every item.

Time complexity: O(1)

O(n): Linear Time

The running time grows directly with the input size.

def find_item(items, target):
for item in items:
if item == target:
return True
return False

In the worst case, the function checks every item.

Time complexity: O(n)

O(log n): Logarithmic Time

The input becomes smaller during each step.

A common example is binary search.

Time complexity: O(log n)

If a search space is divided in half again and again, the algorithm often has logarithmic time complexity.

O(n log n): Linearithmic Time

This complexity often appears in efficient sorting algorithms, such as merge sort.

An algorithm may process all 𝑛 n items while also dividing the problem into smaller parts.

Time complexity: O(n log n)

O(n²): Quadratic Time

The algorithm performs an operation for every pair of items.

def show_pairs(items):
for first in items:
for second in items:
print(first, second)

Both loops run n times 𝑛 × 𝑛 = 𝑛²

Time Complexity : 𝑛²

How to Calculate Complexity of Loops

A Loop That Increases by One

i=1

while i < n:
	print (i)
    i*=2

The value doubles after every step: 1, 2, 4, 8, 16, ...

The number of steps is about log ₂ n.

Time Complexity : O (log n)

Two Nested Loops With Different Sizes

   for i in range (n):
   	for j in range (m):
		print (i, j)

The Outer loop runs n times

the inner loop runs m times

Therefeore o(nxm)=O(nm)

Do not always replace both variables with . If the input sizes are different, keep both variables.

How to Calculate Recursive Time Complexity

Recursion can be more difficult to analyze.

Consider this function:

def countdown(n):
    if n==0:

        return 
  
   print(n)
countdown(n - 1) 

The function calls itself once for each value of 𝑛. 

Therefore: 

<code>Time complexity: O(n)</code>

Now consider a function that makes two recursive calls: 

    def example(n):
        if n <=1: 
            return 
    example(n - 1) 
    example(n - 1) 
    

The number of calls grows very quickly. Its time complexity is approximately: <code>O(2ⁿ)</code>

When analyzing recursion, ask:

• How many recursive calls are made?
• How much does the input shrink each time?
• Is there one recursive call or more than one?
• Is the result stored and reused?

Best, Average, and Worst Cases

An algorithm can behave differently depending on the input.

Best Case

The algorithm finishes as quickly as possible. For example, a search function may find the target in the first position.

Average Case

The algorithm takes an average amount of time for typical input.

Worst Case

The algorithm takes the most time possible. For example, a search function may find the target at the last position or not find it at all. When people discuss Big O notation, they often mean the worst-case time complexity.

Time Complexity Rules to Remember

These rules make calculations easier:

• A single statement is usually 𝑂 ( 1 ).
• A loop that runs 𝑛 n times is usually 𝑂 ( 𝑛 ).
• Nested loops are usually multiplied.
• Separate sections are added.
• Constants are removed.
• Keep the fastest-growing term.
• A loop that repeatedly divides the input often has 𝑂 ( log ⁡ 𝑛 ) complexity.
• If an algorithm handles two input sizes, use 𝑂 ( 𝑛 𝑚 ) when appropriate.

Worked Example

Consider this code:

    def process(numbers):
         for number in numbers: 
            print(number) 
        for i in range(len(numbers)): 
        for j in range(len(numbers)): 
            print(i, j) 
    

Let the number of items be 𝑛.

The first loop has: 𝑂 ( 𝑛 )

The nested loops have: 𝑂 ( 𝑛 2 )

Together: 𝑂 ( 𝑛 ) + 𝑂 ( 𝑛 2 )

The 𝑛² term grows faster than the 𝑛 n term, so we remove 𝑂 ( 𝑛 ) O(n).

Final answer: Time complexity: O(n²)

Time Complexity vs Space Complexity

Time complexity measures how much time an algorithm needs. Space complexity measures how much extra memory it needs.

For example:

def copy_items(items): 
    result=[] 

    for item in items:
     result.append(item) 
return result

The function processes every item, so its time complexity is: O(n) It also creates a new list containing 𝑛 items, so its extra space complexity is: text O(n)

These are different measurements, but both are important when evaluating an algorithm.

Frequently Asked Questions

Is O(1) always faster than O(n)?

Usually, yes for large inputs. However, actual speed can depend on the hardware, programming language, and operations being performed.

Are constants ignored in Big O?

Big O focuses on how an algorithm grows as the input becomes very large. Constants have less effect on growth than terms such as 𝑛 n, 𝑛 2 n 2 , or 2 𝑛 2 n .

What is the fastest time complexity?

𝑂 ( 1 ) O(1) is generally considered the most efficient common time complexity. However, an 𝑂 ( log ⁡ 𝑛 ) O(logn) algorithm can also be very fast for large inputs.

Is O(n²) always bad?

Not always. For small inputs, an 𝑂 ( 𝑛 2 ) O(n 2 ) algorithm may work well. It becomes a problem when the input size grows.

How do I analyze a loop that runs from 1 to n?

If it increases by one each time, it usually has 𝑂 ( 𝑛 ) O(n) time complexity.

To calculate time complexity, identify the input size, count repeated operations, analyze loops and recursion, combine the terms, and remove constants.

The most important patterns are:

• One operation: 𝑂 ( 1 ) O(1).
• One loop: 𝑂 ( 𝑛 ) O(n).
• A loop that halves the input:𝑂 ( log ⁡ 𝑛 ).
• Nested loops: 𝑂 ( 𝑛 2 ) O(n 2 ).
• Efficient sorting: often 𝑂 ( 𝑛 log ⁡ 𝑛 ).

With practice, you can look at a piece of code and quickly estimate how its running time will grow.