Big-O notation in Java

Question

Hey guys can someone explain the big o notation for each of the following examples? Thanks in advance

Reading the element at index 28 in an array. Is this O(1)?
Comparing two ArrayList objects to determine if they contain the same elements (disregarding order, and without sorting). Is this O(n^2)? Searching for a specific target value in an unsorted array. Is this O(n)

These concepts don't change with language. They are universal. So your answers are right in every language. — Sidharth Mudgal, Oct 08 '12 at 22:27
Possible duplicate of [What is a plain English explanation of “Big O” notation?](http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) — The SE I loved is dead, Oct 17 '16 at 19:49

score 1 · Answer 1 · answered Oct 08 '12 at 22:32

Since you have an array, that means contiguous memory. This entails that a lookup at any given index will be in one action, since there is no need to iterate through as in a linked list. So It is O(1).

Comparing two ArrayList objects, A and B, without ordering or sorting is O(n^2) because each element in ArrayList A has to compare with each element in B. So there are n elements in A, n elements in B. That will lead to every element in A requiring n comparisons with B. Since there are n elements in A, that is n comparisons n times, O(n^2).

Although if you used a sorting algorithm, it will be as fast as the sorting algorithm such as O(n log n) time or O(n) depending on the sorting algorithm used.

Searching for a specific target value in an unsorted array is indeed O(n). This is the case because you have to search through every element in the array to check if it exists. Since there are n elements in the list, that means there are n comparisons.

score 1 · Accepted Answer · answered Oct 08 '12 at 22:33

1- Because array elements can be accessed randomly (no need to move from one cell to another like linked list) so you can basically say array[28] which is O(1)

2- comparing two array list can done in a way which will lead to a a lower big-O But with sorting.

You can sort each arraylist using mergesort or quicksort O(nlg(n)) then compare the two sorted lists in O(n). the result is O(nlgn).

But another algorithm (without sorting) would iterate over each element in one array (n). And then checks whether the element is another array (n) (and marks it to handle duplicates properly). This latter algorithm is O(n^2).

3- Yes it's. You have to go through the whole list one by one till you find the desired element.

Big-O notation in Java

2 Answers2