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

steven

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?

3 Replies

Know the answer? Post it — somebody with the same question will find it here.

Vulpes15y ago
Accepted 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.
Vulpes15y ago
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 Bhat15y ago
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.