286 views

Time complexity of the optimal algorithm to interchange the $m^{th}$ and $n^{th}$ elements of a singly Linked List  is

1. $\Theta(m+n)$
2. $\Theta(m)$ when $m\geq n$ otherwise $\Theta(n)$
3. $\Theta(m)$ if $m \leq n$ otherwise $\Theta(n)$
4. $\Theta(m+ \min (m,n))$

To interchange the mth and nth elements of a singly Linked List  we have to fetch each mth and nth element. amd then swap.
Complexity will be O(max (m,n)) for searching and O(1) for swapping.

O(max(m,n))

Difference between option a and b?

@Tesla!! But are we changing the links of these two nodes of linked lists or just the value of variables inside them?!

@shraddha priya you can change link as well as value it doesn't matter

Say m < n.

1. Traverse up to m.
2. Introduce a duplicate pointer from there, and traverse up to n.
3. Swap values using some temporary variable.

Hence, it takes O(n) time, when n>m

So, Option B.

Option A is also correct.

https://stackoverflow.com/questions/19455942/understanding-time-complexity-of-omaxm-n