A precarious one

Computer Science Level 1

Given a singly linked list of size $n>10$ what is the time complexity of finding the 10th element form the front and the 10th element from the end respectively?

Image Credit: Wikipedia.

O(n)

and

O(n)

O(1)

and

O(n)

O(n)

and

O(1)

O(1)

and

O(1)

1 solution

Beakal Tiliksew
Oct 7, 2015

From the front we traverse $10$ node which is $O(1)$

But $10$ th element from the back means $(n-10+1)$ th element from the front which is $O(n)$

The thing to understand is that the big-oh is a measure of the asymptotic growth.

Note that if it's a circular-doubly-linked list, then the time complexity of finding the element at any given position is always $O(1)$ .

Prasun Biswas - 5 years, 8 months ago

A precarious one

Image Credit: Wikipedia.

1 solution

0 pending reports