565 views
3 votes
3 votes

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))$

2 Answers

Best answer
7 votes
7 votes
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))
selected by
Answer:

Related questions

2 votes
2 votes
2 answers
2
Bikram asked Oct 4, 2016
347 views
$$T(n) = \begin{cases} 4 & \quad if \: \: n =1 \\ T(n-1) + 4 & \quad otherwise \end{cases}$$Value of $T(1000)$ is ___