CODEWITHSUNDEEP
time-complexitybig-o
NoName
NoName

Reputation: 10324

How to calculate time complexity with variable list elements?

I got a really long time complexity for this function, not sure if we can simplify it.

# Let n = # of file names in the input
# Overall Time Complexity: O(n + k_0 + k_1 + k_2 + ... + k_n + 1) = O(n + k_0 + k_1 + k_2 + ... + k_n)
def split_input(input):

    # Time Complexity: O(n)
    file_names = input.split(",")

    # Let k_i = file name length for the i^th element
    # Time Complexity: O(k_0 + k_1 + k_2 + ... + k_n)
    for index, value in enumerate(file_names):
        # O(k_i)
        file_names[index] = file_names[index].strip()

    # Time Complexity: O(1)
    return file_names

Upvotes: 1

Views: 34

Answers (1)

Berthur
Berthur

Reputation: 4495

You have already defined n here as the total length of your input string, which includes all your file names, so

n > k_0 + k_1 + ... + k_n.

Therefore, your time complexity is just O(n).

Upvotes: 1

Related Questions