Big O complexity of the cases (answers provided- confirmation would be awesome!) [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 9 years ago.

Improve this question

Question:
We have a chain (or a linked list) of integers with 2-field records: an integer field and a pointer field. If there are n items in a given list, what is the Big O complexity of each of the following cases? -- Note that the chain is not implemented as an array. --

Add an item (to the end of the chain)
O(1).
Add an item (at some position in the chain)
O(n).
Find whether or not the chain is empty
O(1).
Check to see if the chain contains a given integer
O(n).
Get an item (i.e. the integer in the integer field) at some position in the chain
O(n).

I believe the answers that i've got are correct but confirmation from an expert would make my day :) Thank you for your time

Answer 1

Add an item (to the end of the chain) O(1).

It depends on the implementation. Usually a classic LinkedList doesn't have a pointer to its last element, so It would be O(n). If we have a pointer to its last element, so yeah, it would be O(1).

Add an item (at some position in the chain) O(n).

Correct.

Find whether or not the chain is empty O(1).

Correct.

Check to see if the chain contains a given integer O(n).

Correct.

Get an item (i.e. the integer in the integer field) at some position in the chain O(n).

Correct.