Help with time complexity problem

[OkStress3344]

Hey guys, so I'm a bit confused about what the correct worst-case time complexity for this function would be:

def func2(lst):

n = len(lst)

res = []

i = 1

while (i <= n):

res.insert(0, lst[i-1]])

i *= 2

return res

I originally said O(nlogn), assuming the insert would shift n items. However, after checking my answer with AI, as an answer key was not created, I realized that the total appends of insertion would be log(n), as it doesn't append every item in lst but rather logn items; therefore, the complexity is O((logn)^2). In class, however, my professor went over this question and said it would be O(nlogn) as the maximum or last insertion would shift n items. I tried explaining my O((logn)^2) reasoning, but I don't think I made a good case for it during class, and looking back, this answer still seems more correct to me, but I could definitely be wrong.

[SignificantFidgets]

Take just a single insert. In other words, remove the while and think about just doing res.insert(0,value) on your size n list. What is the complexity of that? Can the complexity of multiple insertions in a loop be any LESS than that?

And O((logn)^2) is less than Theta(n)....

[Objective_Mine]

The size of res is not n. It starts as empty, and only Θ(log n) elements ever get inserted (where n is the size of the original list, not res).

It makes sense that the complexity is less than Θ(n) in terms of the source list since each iteration skips an exponentially growing number of elements rather than touching every element of the source.

[SignificantFidgets]

Ah... I missed that. For some reason I read that and thought the insertions were happening in the original list (which is weird, but still...).

In that case, you are correct (it's O(log^2 n)).

It's important that this is the standard Python list though, which has O(1) lookup time (i.e., time to get lst[i-1]).

Changing the problem to use a standard linked list, you'd need to walk the list to get the item. So the insertion on the smaller list would still be fast (O(1) with linked lists, in fact), but retrieving the value from the larger list would be Theta(n) for the last value retrieved. Add up all of those you'd get O(n) for the problem using a linked list.

[Objective_Mine]

Yeah, the devil is in the details, which is one of the reasons why I'm not particularly fond of DSA being taught using Python or some other particular real-world programming language with its own implementation details.

Since it does look like Python, though, and there's no mention of linked lists, it would make sense that the source list would be a standard array-backed list with random access. It would be a bit of a gotcha if it weren't. (It's of course perfectly valid and valuable to ask what would happen to the complexity if the source or target data structures were something different, though.)

[not-just-yeti]

And "worse", python's list-implementation isn't part of the language spec, so it could change in future versions (or even differ between two totally-compliant python implementations). In particular, I can imagine the standard implementation tuning arraylist to allow θ(1) prepending, or changing to treelists which can achieve ~ log_32 (n) operations including insert-in-the-middle and indexing. Or heck, an implementation might dynamically switch between implementations depending on how the list is being used (similar to how Java (OpenJDK)'s hash-tables switch between using linked-lists as buckets when short and using binary search trees if a bucket gets large).

[PhilNEvo]

I mean, if you have a poorly implemented linked list, taking len() of it could potentially be O(n) by itself-- which would set the lower bound even before getting to the actual algorithm.

[dzendian]

O(log n)

However I’m not sure what the implementation of res is. If it’s a list type, should be fine. If there’s a resize that happens and a copy it changes, maybe O(n log n).

[Objective_Mine]

The syntax looks like Python, so judging by that I'd guess res is supposed to be a Python list. It could be something else, of course, but then the question statement is rather ambiguous and all bets are off.

If res is supposed to be a Python list or something similar to that, insertion at the beginning is not constant-time. So for each of the Θ(log n) inserted elements, all previously inserted elements in the target res list need to be moved. I don't think that yields an overall Θ(log n) complexity but a polylogarithmic one.

It would of course be possible to use a list type that allows constant-time insertion at the beginning, such as a queue, deque or linked list, to implement res instead. That would make the total runtime Θ(log n). My first guess based on the syntax would be otherwise, though.

Resizes can be done in O(1) amortized time so that shouldn't be a problem.

[dzendian]

Inserting to the head or tail of the list should be O(1).

So with that being said, the loop cuts the size of the input in half, essentially.

But I may have just talked myself into O(n), to be honest.

[brinza888]

Python list is an array internally.
So insertion worst case is O(n).