Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Can there be a genuine algorithm in which number of memory reads far outnumber the no. of operations performed? For example, number of memory reads scale with n^2, while no. of operations scale with only n, where n is the input size.
If yes, then how will one decide the time complexity in such a case? Will it be n^2 or only n?
For a memory read to be relevant to the algorithm, the information read in must be processed in some way.
If the information is never compared or used as input to any operator, it will not affect the algorithm and thus was unnecessary to read in the first place.
If there were an operator that could accept a variable number of inputs, a number that could grow without bounds, then and only then could you have the number of memory reads far outnumber the number of operations in the way you describe. For instance, if "sum" were a single atomic operation accepting any number of inputs, then you could have such an algorithm.
However, a model of computation where a single operation could utilize an unlimited number of inputs is not very interesting nor very useful for algorithmic analysis. It would essentially just push all the hard work to a lower level of abstraction. So you won't find such a model in any CS literature.
A paragraph from an MIT Open CourseWare PDF about communication networks as in Graph Theory makes a related point (related to what I said about just pushing the hard/interesting work to a different level of abstraction) in discussion of switch sizes:
One way to reduce the diameter of a network (and hence the latency needed to route packets) is to use larger switches. For example, in the complete binary tree, most of the switches have three incoming edges and three outgoing edges, which makes them $3 \times 3$ switches. If we had $4 \times 4$ switches, then we could construct a complete ternary tree with an even smaller diameter. In principle, we could even connect up all the inputs and outputs via a single monster $N \times N$ switch, as shown in Figure 6.9. In this case, the “network” would consist of a single switch and the latency would be $2$.
This isn’t very productive, however, since we’ve just concealed the original network design problem inside this abstract monster switch. Eventually, we’ll have to design the internals of the monster switch using simpler components, and then we’re right back where we started. So the challenge in designing a communication network is figuring out how to get the functionality of an $N \times N$ switch using fixed size, elementary devices, like $3 \times 3$ switches.
If you follow D.W.'s definition, a "memory read operation" is an operation and can read only one item from memory, so from that definition alone the number of operations must be the same or larger than the number of items read from memory. Let's assume that "reading memory" doesn't count as an operation.
If you read a memory location, and you do anything with it, including deciding whether to use it or not, that will be at least one other operation. So even if we don't count the memory read itself as an operation, you can only have more reads than other operations if you read memory "just for fun", that is the algorithm would have worked exactly the same if you hadn't read the memory.
Even if we accept that you might be reading memory "just for fun", this cannot change the big-O behaviour of the algorithm. That's because your algorithm can only have a finite number of read operations, so the number of reads could only be larger than the number of other operations by a constant factor. As soon as you have a loop, you have other operations controlling the loop. As an example, in the C language you could have a loop like
for (i = 0; i < n; ++i) { x; x; x; x; x; x; x; x; x; x; x; x; x; }
Assuming that the expression x; reads memory without any other operations, you still have only a dozen read operations per loop, so you still have O (n) operations to perform the loop, and O (n) read operations. The constant factor could be arbitrarily large, I could add a billion read operations in the loop, but that doesn't change the big-O behaviour.
No. In standard models of computation, each operation can read at most a constant number of memory locations. Therefore, the number of memory reads is at most $O(n)$, where $n$ is the number of operations.
If you assume that one memory-read corresponds to a single operation performed, then the number of memory reads may not outnumber the number of operations performed. This assumption is usually made in theory of computability and complexity theory.
As for complexities, there are two main computational complexities: SPACE complexity and TIME complexity which are actively studied in Computer Science.
An algorithm's time complexity is defined by the maximum rate at which any
operation grows with respect to the problem size n. Thus, memory accesses
will define the complexity of an algorithm if they increase at the fastest rate
with respect to n. Thus the time complexity is $O(n^2)$ in your case.
As a note, memory accesses are quite expensive in practice, and in sparse linear algebra and graph processing codes often represent the bulk of the run time.
