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?

Practice

1. What does the reversed() function do in Python?

easy

A. It sorts the items of a sequence in ascending order.

B. It returns an iterator that goes through the items of a sequence backwards.

C. It removes duplicate items from a sequence.

D. It changes the original sequence to its reversed form.

Solution

1. Step 1: Understand the purpose of reversed()

   The reversed() function returns an iterator that accesses the elements of a sequence in reverse order.

2. Step 2: Check if original sequence changes

   The original sequence remains unchanged; reversed() only provides a way to loop backwards.

3. Final Answer:

   It returns an iterator that goes through the items of a sequence backwards. -> Option B

4. Quick Check:

   reversed() returns reversed iterator [OK]

Hint: Remember: reversed() does not change original, just reads backwards [OK]

Common Mistakes:

• Thinking reversed() sorts the sequence
• Assuming reversed() modifies the original sequence
• Confusing reversed() with removing duplicates

2. Which of the following is the correct way to use reversed() to print characters of a string backwards?

easy

A. for ch in reversed('hello'): print(ch)

B. for ch in reverse('hello'): print(ch)

C. for ch in 'hello'.reversed(): print(ch)

D. for ch in reversed['hello']: print(ch)

Solution

1. Step 1: Identify correct function syntax

   reversed() is a built-in function called with parentheses and a sequence inside, like reversed('hello').

2. Step 2: Check loop syntax

   The for loop correctly iterates over the reversed iterator returned by reversed().

3. Final Answer:

   for ch in reversed('hello'): print(ch) -> Option A

4. Quick Check:

   Use reversed() with parentheses and a sequence [OK]

Hint: Use reversed() with parentheses, not square brackets or dot calls [OK]

Common Mistakes:

• Using square brackets instead of parentheses
• Calling reversed as a method on string
• Typing reverse instead of reversed

3. What is the output of this code?

print(list(reversed([1, 2, 3, 4])))

medium

A. Error: reversed() cannot be used on lists

B. [1, 2, 3, 4]

C. [4, 3, 2, 1]

D. [1, 4, 3, 2]

Solution

1. Step 1: Apply reversed() to the list

   reversed([1, 2, 3, 4]) returns an iterator that goes through the list backwards: 4, 3, 2, 1.

2. Step 2: Convert iterator to list

   Using list() on the reversed iterator collects all items into a new list in reversed order.

3. Final Answer:

   [4, 3, 2, 1] -> Option C

4. Quick Check:

   list(reversed([1,2,3,4])) = [4,3,2,1] [OK]

Hint: Wrap reversed() with list() to see reversed items as a list [OK]

Common Mistakes:

• Expecting reversed() to return a list directly
• Confusing reversed() with sort()
• Thinking reversed() modifies original list

4. What is wrong with this code?

my_str = 'abc'
rev_str = reversed(my_str)
print(rev_str)

medium

A. It prints a reversed iterator object, not the reversed string.

B. It prints a reversed string directly.

C. It causes a syntax error because reversed() needs a list.

D. It modifies my_str permanently.

Solution

1. Step 1: Understand what reversed() returns

   reversed(my_str) returns an iterator, not a string.

2. Step 2: Printing the iterator shows its object info

   Printing rev_str directly prints something like <reversed object at ...>, not the reversed characters.

3. Final Answer:

   It prints a reversed iterator object, not the reversed string. -> Option A

4. Quick Check:

   reversed() returns iterator, print shows object [OK]

Hint: Convert reversed() result to list or string before printing [OK]

Common Mistakes:

• Expecting reversed() to return a string
• Trying to print reversed() result directly
• Thinking reversed() modifies original string

5. How can you use reversed() to create a new string that is the reverse of the original string s = 'Python'?

hard

A. new_s = s.reverse()

B. new_s = reversed(s)

C. new_s = s[::-1]

D. new_s = ''.join(reversed(s))

Solution

1. Step 1: Use reversed() to get reversed iterator

   reversed(s) returns an iterator over characters of s in reverse order.

2. Step 2: Join characters into a new string

   ''.join(reversed(s)) combines the reversed characters into a new string.

3. Final Answer:

   new_s = ''.join(reversed(s)) -> Option D

4. Quick Check:

   Use join() with reversed() to build reversed string [OK]

Hint: Use ''.join(reversed(s)) to reverse strings easily [OK]

Common Mistakes:

• Assigning reversed(s) directly to string variable
• Using s.reverse() which is invalid for strings
• Confusing slicing with reversed()