Asymptotic time complexity for finding maximum element in an array

Question

Consider a simple algorithm to find the maximum element of an array containing integers. We just loop through the array, storing the maximum found so far and updating it whenever an element larger than the existing maximum is encountered.

This algorithm is often considered to have $O(N)$ complexity. But doesn't accessing the array take $O(\log N)$ time in each iteration of the for loop? After all, an array of size $N$ requires $\log N$ address bits, so accessing each element should take $\log N$ time steeps? So the total time complexity should be $O(N \log N)$, unless I'm missing something here?

Answer 1

The usual model of computation used to analyze algorithms is the unit-cost RAM model, in which machine words have width $O(\log n)$, and operations on machine words (including dereferencing) take constant time.

In this model of computation, you can find the maximum of an array of length $n$ words in linear time.

Answer 2

In most analyses, reading a $\log n$ length pointer (where $n$ is the pointer) is defined to be constant time ($O(1)$), therefore finding the maximum is $O(N)$.

Also, you are mixing variables here. The $N$ refers to the number of elements in the array, but when you say $\log N$, you really mean the number of bits to represent a pointer to some array element.

• user308485: Would the number of bits needed to represent the array not be logarithmic in the size of the array (in the worst case)?
• ydh28: It would, but you don't read integers bit by bit on most computer architectures. Many theoretical computation models used in algorithmic analysis also define memory access given an explicit address as $O(1)$.

Answer 3

It all depends on the model of computation. Usually, array elements are taken to be a fixed size and stored contiguously, so you can simply move the tape head, disk platter, etc. by that constant amount in each step.

In case you need to maintain the address of the location pointed to, incrementing an $O(n)$-bit value by the same constant on $n$ different occasions takes $O(1)$ amortized time per increment in most reasonable models of computation (proof: consider the number of times various right-most bits change; can you find the geometric series?).