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.

nanosoft
  • 2,913
  • 4
  • 41
  • 61
  • 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) – awksp May 26 '14 at 05:56
  • Can you point me to some links which says so? – nanosoft May 26 '14 at 06:12
  • Not sure how much this helps, but there's [this](https://stackoverflow.com/questions/20615908/array-access-complexity). 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. – awksp May 26 '14 at 06: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. – johncip May 26 '14 at 06: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. – nanosoft May 26 '14 at 06:46

3 Answers3

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).

Gallo2fire
  • 153
  • 1
  • 9
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.

Community
  • 1
  • 1
Abs
  • 3,902
  • 1
  • 31
  • 30
0

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

TheLostMind
  • 35,966
  • 12
  • 68
  • 104