Question

I have a function and I was tild to give the big o notation of it
Analyze the worst-case run-time complexity of the member function reverse() of the List. Give the complexity in the form of Big-O. Your analysis can be informal; however, it must be clearly understandable

template <typename T>

void List<T>::reverse() {

auto current = head; // starting from head node

  while(current != nullptr) // till current node is not last (next after last)

  {

    std::swap(current->next, current->prev); // swap 'next' and 'prev' pointer values

    current = current->prev; // advance next node (we use 'prev' because we swap it before)

  }

  std::swap(head, tail); // swap 'head' and 'tail' nodes

}

Answer 1

Well The worst time complexity for reversing the list would be O(n).

The possible explaination i can give is :

Time complexity refers to how much time would the program take to complete.

Now suppose there is a list with 1 element how many operation would it take to reverse it .It would be one.

Now suppose there are 2 elements in list you have to reverse 2 elements so the time complexity will be dependent on reversing those two elements.

Now in worst case if there are n elements in list how much operation would it take to reverse n elements

The answer is n.So time complexity is O(n) because we need to iterate through whole list i.e process n elements.

Next example will make it more clear:

Suppose there is a nested loop such as

for(int i = 1; i <= n ; i++)

{

for(int j = 1; j <= n ; j++)

{}

}

How will you measure the time complexity of such a program

Now lets take i = 1 how long will i stay 1 it would be untill j goes from 1 to n.

after that i would become 2.

similarly when i =2 when will i become 3.

when j goes from 1 to n.

SO what can we conclude

for every i we have n operation in the inside loop

so in worst case if i = n it will take n*n time i.e O(n^2)

So we can say that in above given code while reversing we have to do n operations (n = no of elements in list)

So time complexity would be O(n).