educative.io

Time complexity of range(n) & print(sum)

Courses
,
#1

To instructors, can you please explain in more detail
(1) What is the time complexity of range(n) without the for loop? And why so?
(2) Why is time complexity of print(sum) = 1? shouldn’t it be 2 primitive operations? = 1 for fetching value of sum and 2nd for printing it?

image
image1726×1434 167 KB

Course: Algorithms for Coding Interviews in Python - Learn Interactively
Lesson: Comparing Algorithms - Algorithms for Coding Interviews in Python

#2

Hi @adityahpatel!!
Let’s break down your questions step by step:

  1. Time complexity of range(n) without the for loop:

    The range(n) function in Python creates a sequence of numbers from 0 to n-1. However, it doesn’t actually generate all the numbers in the sequence upfront. Instead, it generates them dynamically as they are needed. This means that the time complexity of range(n) without the for loop is O(1).

    Here’s why:

    • When you call range(n), Python simply initializes the range object with the start (0), stop (n-1), and step (default is 1) values. This initialization process takes constant time regardless of the value of n.
    • The range object itself doesn’t contain the actual sequence of numbers. It generates them on-the-fly when you iterate over it or access its elements. Thus, the time complexity of initializing the range object is constant, O(1), because it doesn’t depend on the size of n.

  2. Time complexity of print(sum):

    The time complexity of print(sum) is indeed O(1), not O(2). This is because the time complexity notation doesn’t count primitive operations like fetching the value of a variable or function argument. Instead, it focuses on the algorithm’s behavior as the input size grows.

    Here’s why the time complexity of print(sum) is O(1):

    • Printing a value to the console is typically considered a constant-time operation because it doesn’t depend on the size of the value being printed or any other input. It involves sending the value to the standard output stream (stdout), which is usually handled efficiently by the operating system and underlying I/O mechanisms.
    • Fetching the value of sum is also considered a constant-time operation because it involves accessing a single memory location where the value is stored. Accessing a specific memory location is typically considered constant-time, regardless of the size of the memory or the value stored in it.

    Therefore, the time complexity of print(sum) is O(1), indicating that the time it takes to execute this operation remains constant regardless of the size of the input or the value of sum.
    I hope it helps. Happy Learning :blush:

1 Like