Linked list Quiz

Question

Consider an unrolled linked list with $n$ elements.This list stores multiple elements in each node.
What is the worst case time complexity to find the $k^{th}$ element if the number of nodes and the
number of elements in each node are equal?
$A)O(n)$                                $B)O(\sqrt n)$
$C)O(nlogn)$                      $D)O(n^{2})$

Comments

Yes

can you explain?

---

"unrolled linked list with n elements"

Let n=25

Considering below point

"the number of nodes and the number of elements in each node are equal"

there are x nodes and size of each node is x for storing 'n' elements.

so x*x=> 25=> x=5

i.e. we have 5 nodes each with 5 elements.

"What is the worst case time complexity to find the kth element" 

let the kth element be the $25^{th}$ element then we need to traverse all the 4 nodes + 4 elements in last node.

Generalizing this for $k^{th}$ element with $n$  elements we need to traverse $n^{1/2} -1$ nodes + $ n^{1/2} -1$ elements

So time complexity = $O(√n)$

Correct me if any mistakes.

---

An unrolled linked list contains more than 1 element in each node.

The question asks to find some kth element, and if the no. of nodes and the no. of elements in each node are equal then n should be a perfect square. If in each node there are m elements then there has to be m nodes each of containing m elements, this implies total elements will be m².

So in the given question if there are n elements then each node must be having $\sqrt{n}$ elements. if each node is having $\sqrt{n}$ elements then there has to be such $\sqrt{n}$ nodes. so the complexity to reach last node becomes O($\sqrt{n}$) as we need to search to max $\sqrt{n}$ nodes to find desire element.

1. How to find node in which kth element is present?

-> $\lceil$$K/$$\sqrt{n}$ $\rceil$

2. How much time it will take to reach that node ( there are max $\sqrt{n}$ nodes)

-> $\sqrt{n}$

3. Once the node is reach how much time it will take search that element in that node

-> $\sqrt{n}$ = as there are total $\sqrt{n}$ elements in each node

So Overall time complexity becomes

= Time to reach that node + Time to search that element

=  O($\sqrt{n}$+$\sqrt{n}$) = O($\sqrt{n}$) .