2

I have one very basic question. In java(or I think valid for any similar language), what's the retrieval time of an element from an array. Since the size of array and its element type is a constant known at compile time or computed at run-time, I believe that retrieval should happen in constant time, O(1). For example,

int[] arr = new int[10];

Though I am not sure of internal memory representation of array, I think operation like arr[3], should directly access memory after calculating address from array start address, size of element type(here 32) and index passed(here 3) something like below:

address of arr[3] = address of a[0] + 32 * 3.

Thanks for the help.

Improve this question
5
  • 2
    If memory serves, that's actually pretty close to how array accesses happen in C/C++. I'm not sure what Java does internally, but I'm fairly certain that array accesses are always O(1) Commented May 26, 2014 at 5:56
  • Can you point me to some links which says so? Commented May 26, 2014 at 6:12
  • Not sure how much this helps, but there's this. I think it's a language-agnostic thing -- all you need to do is perform some math, add it to a pointer, and there's your index. Commented May 26, 2014 at 6:14
  • 1
    The size of the array doesn't need to be known at compile time. For instance, the compiler can't tell you how big new int[(int) System.currentTimeMillis() / 1000] will be. Commented May 26, 2014 at 6:29
  • Agreed @johncip, that in java atleast size of array need not be a compile-time constant. Nice catch. Even though the value is computed at run-time and memory allocation happens at run-time, the access time seems like constant, from the discussions till now. Commented May 26, 2014 at 6:46

3 Answers 3

Reset to default
0

This is a classical case of Memory vs Computation power:

For Java:

It will be constant time as long as the array size is small enough and stored on JVM Heap.

Otherwise it will depend on factors like your implementation of large data-sets using concurrency fork join/parallel programming .

Also worth looking at is how memory allocator would work for the language in question for the time cost bringing it in process again object size is the big player.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

like user3580294 said it should be O(1) because you are giving it the exact place you want to look in the array instead of iterating through which of course is O(n).

Improve this answer

Comments

0

Yes its O(1). More precisely It is : O(k*1)) where k -- >some machine dependent constant

Improve this answer

3 Comments

Doesn't the O(1) already imply the machine-specific constant?
@user3580294 - It does. I just wanted to point out the fact that there will always be some dependency on the underlying machine.
So shouldn't it more properly be (k * 1)?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.