0

One interview question which I couldn't answer and couldn't find any relevant answers online.

I know the arraylist retrieve the data in constant time based on the indexes.

Suppose in an arraylist, there are 10000 data and the element is at 5000th location(We are not given the location), we have to search for a particular value( for eg integer 3 which happens to be on the 5000th index), for searching the value, we will have to traverse through the arraylist to find the value and it would take linear time right??

Because if we are traversing through the arraylist to find the data, it would take linear time and not constant time.

In short I want to know the internal working of contains method in which I have to check for the particular value and I don't have the index. It will have to traverse through the array to check for the particular value and it would take O(n) time right?

Thanks in advance.

neil
  • 149
  • 1
  • 12
  • index-based retrieval takes constant time. searching a particular value is linear (unless the array has been sorted, in that case you apply bin.search taking `O(logn)` time). is there a possibility that you've misunderstood the question? maybe some additional details were given – mangusta Aug 28 '18 at 01:33
  • @mangusta. the interviewer asked me the question about the difference between arraylist and linkedlist to which I told him that linkedlist is good for insertion and deletion as it takes constant time whereas arraylist takes O(1) for searching. I told that arraylist search works on indexing due to which it takes constant time. then he asked suppose the element is at 5000th location, you have to search from index 0, it will also take linear time. how do say it takes O(1) ? – neil Aug 28 '18 at 01:44

1 Answers1

0

I hope this is what you want to know about search in ArrayList:

Arrays are laid sequentially in memory. This means, if it is an array of integers that uses 4 bytes each, and starts at memory address 1000, next element will be at 1004, and next at 1008, and so forth. Thus, if I want the element at position 20 in my array, the code in get() will have to compute: 

1000 + 20 * 4 = 1080

to have the exact memory address of the element. Well, RAM memory got their name of Random Access Memory because they are built in such way that they have a hierarchy of hardware multiplexers that allow them to access any stored memory unit (byte?) in constant time, given the address.

Thus, two simple arithmetic operations and one access to RAM is said to be O(1). See link to original answer.

Grygorii
  • 162
  • 2
  • 6