Question

What are the time complexities of finding 10th element from the beginning and 7th element from the end

Answer 1

Answer:

Step-by-step explanation:The concept has been explained above by Anders for the 8th element from the beginning.

For the 8th element from the end of the list we can use two pointers. Both of them start from the beginning of the list and then we move one of the two by following 7 nodes so that the two pointers have a difference of 8 nodes (including the nodes where they are pointing to).

From that point and on you iterate so that in every step we move each pointer by one position; first we are moving the pointer that is further ahead of the two. When we can not move that pointer further (say because the next pointer is null), then we stop. At that point, the other pointer is pointing to the 8th element of the list counting from the end.

So, total complexity is the number of assignments that we have performed to the pointers by following the `next' links of the list which is n+(n−8)=2n−8n+(n−8)=2n−8, which is O(n)O(n).