Is this O(1) or O(n)?

[hshivaraj]

Hey all.
Im trying to get this right. Please correct me if my understanding is right or if your agree.
I think the following code has time complexity of O(1) and a space complexity of O(n). Do you agree?

def zigzag(str1, str2):
    minum = min(len(str1), len(str2))
    output = [None] * minum * 2
    output[::2] = str1[:minum]
    output[1::2] = str2[:minum]
    return ''.join(output) + str1[minum::] + str2[minum::]


def main():
    str1 = "abcdefgh"
    str2 = "1111"
    print(zigzag(str1, str2))


if __name__ == "__main__":
    main()

[squenson]

O(1) (n being the length of str1 or str2) would mean that the calculation time is independent of the length of str1 or str2, which is not the case. So for me it is O(n). For space, it is definitively O(n)

[hshivaraj]

O(1) (n being the length of str1 or str2) would mean that the calculation time is independent of the length of str1 or str2

I only came to a conclusion of O(1) because, im not looping through the entire string str1 or str2. Since im using list slicing technique, from an application respective it appears that each line of code in function zigzag was touched once. Do you still believe its O(n)?

I agree with the space complexity.

[Mekire]

Definitely not constant in the size of your input.

Take just this line:

output = [None] * minum * 2

Do you think that is a constant time operation that is unaffected by the size of your strings?
It isn't.
Your slicing is also not constant time.
Your final join is also not constant time.

Just because you didn't explicitly write a loop doesn't make this constant time.

O(n).

[hshivaraj]

Your slicing is also not constant time.
Your final join is also not constant time.

Ok - what i wasn't taking into account here was how the slicing or join method are implemented.
As you can see, I was considering my approach and solely based on that i come to a conclusion of O(1). Which is not the way how the complexity is measured.

Thanks for the clarification.

[wavic]

Just test it. Make the strings one million characters length and you will see.

[micseydel]

Just going to be another person confirming it's O(n) time. Complexity analysis definitely takes into account implementations, regardless of explicit loops - for example, you can't encapsulate something expensive in a function to "cheat" and improve your big-O (which is what would be happening here). Further, it's rare / impossible to use more space than time. It takes proportional time to merely allocate the space, let alone do anything with it, and if you can do it faster than you probably don't need to allocate the space in the first place.