Z
Z
zlodiak2019-02-16 23:01:34
Python
zlodiak, 2019-02-16 23:01:34

How to calculate the complexity of the comparison operation?

#!/usr/bin/env python3

a = [3, 2, 6, 34, 5]    # O(n)
for i in range(5):      # O(n)
    if a[i] > 5:        # ?
        print(a[i])     # O(1)

Please help me calculate the difficulty. I have a problem with a string: as I understand it, two operations will have to be evaluated here (extraction from a dictionary by key and comparison>). Apparently, the calculation of the complexity for this line looks like this?
if a[i] > 5:
O(1) + O(1) = O(2) -> константы сокращаем до единицы -> O(1)

As a result, the complexity of the whole algorithm turned out to be:
O(n) + O(n) + O(1) + O(1) = O(2n) + O(2) -> константы сокращаем до единицы -> O(2n + 1)

Answer the question

In order to leave comments, you need to log in

1 answer(s)
M
Mikhail Makarov, 2019-02-16
@KevlarBeaver

It's not a dictionary, it's a list. They write that in python, access to an element by index has complexity O (1), they don’t know how lists are implemented in it.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question