Is f(n) = n O(n) time or O(1)?

Question

I understand that usually you'd just ignore the coefficient when trying to figure out how complex a given algorithm is, but say I have a variable n in a for loop:

[(n, n) for n in range(1,11)]

, which returns

[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9), (10, 10)]

Isn't this assignment just an O(1) operation? We don't do any manipulation with n whatsoever. Or am I misunderstanding the meaning of it - perhaps the O(n) time describes how long it takes to loop through and make all these assignments?

Context is the following code, which I wrote for a school project.

#Michael Frake, CMSC 350, UMGC, 5/22/2021

print("{:<7} {:<8} {:<8}".format('i','f(i)','g(i)'))
for i in range(21):
    print("-", end="")
print()
for i in range(1, 25, 1):
    f = (i / 2) + 10
    g = i
    print("{:<7} {:<8} {:<8}".format(i,f,g))
    if g > f:
        print("g overtook f when i was ", i)
        break

which returns

i       f(i)     g(i)    
---------------------
1       10.5     1       
2       11.0     2       
3       11.5     3       
4       12.0     4       
5       12.5     5       
6       13.0     6       
7       13.5     7       
8       14.0     8       
9       14.5     9       
10      15.0     10      
11      15.5     11      
12      16.0     12      
13      16.5     13      
14      17.0     14      
15      17.5     15      
16      18.0     16      
17      18.5     17      
18      19.0     18      
19      19.5     19      
20      20.0     20      
21      20.5     21      
g overtook f when i was  21

where I was trying to see if there was a difference in the time complexity of these two functions.

user_826983 · Answer

I think you are confusing the notation a bit. n in O-notation refers to the number of input elements (or number of iterations depending on the inputs). It does not have anything to do with how you name your variables.

So it would rather be:

[(value, value) for value in range(1, n)]  # O(n)

Where n can be chosen arbitrarily hence this simple for-loop runs in O(n). If it was constant, e.g. because you always run exactly 21 elements as it is is in your case, it would be just O(21) = O(1).

[(value, value) for value in range(1, 21)]. # O(21) = O(1)

This would change if we did something like this:

elements = list()

for i in range(n):       # O(n)  -> Depending on "n" (number of inputs)
    for j in range(21):  # O(21) -> Constant
        elements.append((i, j))

This would be denoted as O(n) * O(21) which would be reduced to simply O(n) because the worst-time complexity depends on n, the number of input elements.

Just for completeness, the following would be O(n²):

elements = list()

for i in range(n):       # O(n)
    for j in range(n):   # O(n) 
        elements.append((i, j))

Is f(n) = n O(n) time or O(1)?

1 Answers