0

I'm not sure if this has been asked already, but I ran into a time complexity question and couldn't find an answer to it.

I understand the time to loop through a linked list of size n is O(n), but if that linked list was divided into groups of k, and the heads of each group was stored in a list, what would the time complexity be to use a nested for loop to go through each groups of k in the list. Would it still be O(n)?

Improve this question
1
  • Yes, it would still be O(n). However, if it is to search a specific value (not to visit all nodes), and the values are organised in sorted order, then the grouped version can take benefit from that with jump search Commented Sep 13, 2021 at 15:37

1 Answer 1

Reset to default
1

Yes.

You would still have a O(𝑛) complexity for visiting each node, and have an overhead of O(𝑛/𝑘) to go from one group to the next. So if 𝑘 is a variable, then the complexity is O(𝑛+𝑛/𝑘), and as 𝑛/𝑘≤𝑛 that is O(𝑛).

Search on sorted list(s)

If we alter the question to be about finding a given value in the list(s), then the grouped data structure can benefit from a jump search kind of algorithm, where first the outer list is traversed to find the list that has the right range to have the value. Then only that sublist needs to be traversed. If the groups are evenly spread, and the size of the outer list is approximately that of an inner list, (i.e. √𝑛), then the time complexity for searching a value is O(√𝑛)

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Would stating that it's O(n) because our operation in the double for look is O(k * n/k) = O(n) also be correct? Or is this an incorrect way of getting the same time complexity?
I find that less accurate because it seems to assume that each sublist has a size 𝑛/𝑘, which is not true in most cases.
Ahh, well in the question I meant the list is split into groups of k, so each sublist will be a size of k, except maybe the last which may be equal to or less than k, depending on the remainder. n/k would be the number of sublists. Does this change anything?
In that case it is fine. I updated my answer in the understanding that the number of sublists is 𝑛/𝑘.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.