in Algorithms
283 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))$
in Algorithms
by
283 views

2 Answers

7 votes
7 votes
Best answer
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

4 Comments

Difference between option a and b?
0
0

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

0
0

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

0
0
1 vote
1 vote

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

Answer:

Related questions