Why we say the time complexity of reading element in a Array is O(1)?

Question

WHY we say the time complexity of reading element in a Array is O(1)? There is only once operation? What's it? WHY?

i am thinking, there are many built-in method in .Net library, how we define if it is a basic operation when we check the time complexity?

Vulpes · Answer

O(1) is an example of so called Big O notation (see http://en.wikipedia.org/wiki/Big_O_notation ). It means that the time taken to perform an algorithm is constant regardless of the size of the input data. Reading an array element fits this description. However big the array is the time taken to read a particular element is constant. In general you have to think what's involved in a particular algorithm to decide on its Big O value. There are some examples in the Wikipedia article I've linked to above.

Vulpes · Answer

It's easy to see that the time taken to read an array element is independent of the size of the array by examining what you'd need to do in unsafe code to perform such an operation. As you can see you can read any element by simply setting the value of 'n' to that element - the rest of the code is the same: using System; class Test { unsafe static void Main() { int[] ia = {10 20 30 40}; int n = 4; // or whatever fixed (int* pi = ia) // set pi to point to first element of array { int* pi2 = pi; // use temporary pointer as pi fixed // access nth element pi2 += n - 1; // move pointer to nth element int i = *pi2; // dereference pointer Console.WriteLine(i); // 40 } Console.ReadKey(); } } Reading an array element in 'safe' code does much the same thing under the hood though the code will check that 'n' is not outside the bounds of the array first.

Satish Bhat · Answer

May be reading an element at the specified position is O(1) operation because once we have the position we can directly read it from the position. So it does not depend on the length of the array. MSDN says Array.GetValue Method is an O(1) operation. Whereas Array.Find(T) Method is an O(n) operation where n is the Length of array.