2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Would the number of bits needed to represent the array not be logarithmic in the size of the array (in the worst case)? $\endgroup$ – user308485 Oct 15 '18 at 23:18
  • $\begingroup$ 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)$. $\endgroup$ – ydh28 Oct 15 '18 at 23:22
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.