complexity and big oh notation on algorithms [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 9 years ago.

Improve this question

I need som help understanding how this works! how do I go about calculating the complexity of 'Computing the first half of an array of n items' or 'displaying the third element in a linked list' ? I need someone to explain how this works, theses are just examples, so be free to use your own if it helps explaining! thank you.

Answer 1

You should look at how the processing time of the algorithm grows as the size of the input grows. I'll take your two concrete examples:

Computing the first half of an array of n items

We need to process n/2 items. If n doubles, then the processing time should also double. Consequently, this is a linear operation (i.e. O(n)).

displaying the third element in a linked list

We always want to display the third element, so the size of the list doesn't actually matter. If it doubles, we don't care; the processing time is not affected. Consequently, this is a constant-time operation (i.e. O(1)), it doesn't depend on the size of the input.