Introduction

You cannot assign a meaningful time complexity to a function named fun() from its name alone; the answer depends entirely on what the code does. The correct way to analyze it is to count how often the dominant operations run as the input size grows, then simplify that count into Big O notation.

Core Sections

A Simple Process for Analyzing fun()

When you see a function and need its time complexity, ask:

• What is the input size, usually called n?
• Which operations repeat as n grows?
• Are there nested loops, recursion, or costly built-in operations?
• Which term grows fastest?

Constant-time statements such as assignment, arithmetic, or array access are usually treated as O(1). The complexity comes from how many times those statements execute.

Example 1: One Loop

1def fun(n):
2    total = 0
3    for i in range(n):
4        total += i
5    return total

The loop runs n times, and each iteration does constant work. That gives:

• 'n iterations'
• 'O(1) work per iteration'
• total complexity O(n)

This is the most direct pattern in algorithm analysis.

Example 2: Nested Loops

1def fun(n):
2    count = 0
3    for i in range(n):
4        for j in range(n):
5            count += 1
6    return count

The outer loop runs n times. For each outer iteration, the inner loop also runs n times. So the body executes n * n times, which is O(n^2).

When loops are fully nested and both depend on n, multiply their sizes.

Example 3: Halving or Doubling Loops

1def fun(n):
2    i = 1
3    while i < n:
4        i *= 2

Here i doubles each time. The number of iterations is the number of doublings needed to reach n, which is about log2(n). So the complexity is O(log n).

This pattern appears in binary search and many divide-and-conquer steps.

Example 4: Mixed Growth

1def fun(n):
2    for i in range(n):
3        j = 1
4        while j < n:
5            j *= 2

Now the outer loop runs n times and the inner loop runs O(log n) times for each outer iteration. Multiply them:

O(n) * O(log n) = O(n log n)

This is a common structure in efficient sorting and tree-based algorithms.

Watch the Cost of Operations Inside Loops

A major source of mistakes is assuming every statement inside a loop is constant time. That is not always true.

For example:

1def fun(items):
2    for item in items:
3        if item in items:
4            pass

If items is a Python list, item in items is itself O(n). Since that check is inside a loop over n items, the total complexity becomes O(n^2), not O(n).

So when analyzing a function, include the cost of helper operations, method calls, and data structure behavior.

Recursive Functions

If fun() is recursive, count how many subproblems it creates and how much work happens per call. For example:

1def fun(n):
2    if n <= 1:
3        return 1
4    return fun(n - 1) + 1

This makes one recursive call per level and decreases n by one, so it runs in O(n).

By contrast, a Fibonacci-style recursion that branches into two calls per level grows much faster and can be exponential without memoization.

Common Pitfalls

• Counting lines of code instead of counting repeated work as input size grows.
• Assuming helper operations inside loops are constant time without checking the data structure behind them.
• Forgetting to simplify the final expression down to the dominant growth term.
• Treating the function name as meaningful when the actual code is what determines complexity.
• Confusing asymptotic complexity with actual runtime on small real-world inputs.

Summary

• The complexity of fun() depends on the code, not the function name.
• Count how many times the dominant operations execute as input size grows.
• Multiply for nested loops, add for sequential phases, and watch for logarithmic growth patterns.
• Include the real cost of operations inside loops instead of assuming everything is constant time.
• Simplify the final expression to the highest-growth term for the Big O result.