reversed() function in Python - Time & Space Complexity

Time Complexity: reversed() function

O(n)

Understanding Time Complexity

We want to understand how the time needed to reverse a list grows as the list gets bigger.

How does using the reversed() function affect the work done when the input size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_list = [1, 2, 3, 4, 5]
for item in reversed(my_list):
    print(item)

This code prints the items of a list in reverse order using the reversed() function.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each item in the list once in reverse order.
• How many times: Exactly once for each item in the list (n times).

How Execution Grows With Input

As the list gets longer, the number of steps to go through all items in reverse grows in the same way.

Input Size (n)	Approx. Operations
10	10 steps to print all items
100	100 steps to print all items
1000	1000 steps to print all items

Pattern observation: The work grows directly with the number of items. Double the items, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to iterate and process the list grows in a straight line with the list size.

Common Mistake

[X] Wrong: "reversed() instantly returns the reversed list without any work."

[OK] Correct: reversed() creates an iterator that goes through each item once, so it still takes time proportional to the list size.

Interview Connect

Understanding how built-in functions like reversed() work helps you explain your code clearly and shows you know what happens behind the scenes.

Self-Check

What if we changed reversed(my_list) to my_list[::-1]? How would the time complexity change?