0
$\begingroup$

I am sorry if I sound repetitive(I've asked a similar sounding question earlier - Relevance of memory reads while calculating the time complexity of an algorithm). Actually, it didn't answered my intended query. May be I framed the question inappropriately, and in an unnecessarily complex and indirect way.

In the current/present question, I am referring to the magnetic disk memory as it definitely takes much time, but if the primary memory(RAM) also does take much time relative to processing, then it can too serve the purpose here.

Also, I am specially concerned here with the algorithms where number of memory reads are some function of 'n', instead of being nearly constant(because in latter case, this question is not applicable or doesn't make sense anyway).

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The time-complexity of an algorithm is assessed as though performed on a simple computer with enough (real) memory to hold the program and all the data. The mapping of big data into virtual and real memory is a special different question. As real memories get bigger and bigger, these aspects interfere less and less. $\endgroup$
    – Thumbnail
    Aug 1, 2017 at 19:47
  • $\begingroup$ @Thumbnail I am not referring to the space complexity but the time to read the memory here. $\endgroup$
    – amsquareb
    Aug 2, 2017 at 7:51
  • 3
    $\begingroup$ What is your question? $\endgroup$
    – Raphael ♦
    Aug 2, 2017 at 8:44
  • $\begingroup$ I consider it a problem that many students' lack of awareness of the importance of memory costs and cache performance leaves them unprepared for the real world. The cost of accessing the memory hierarchy is indeed abstracted out of many algorithms. $\endgroup$
    – Ellen Spertus
    Aug 2, 2017 at 20:11

1 Answer 1

Reset to default
4
$\begingroup$

People don't usually refer to the hard drive as "memory" though the term "external memory" is common in this area of the literature. As far as disk accesses are concerned, they are taken into account in the analysis of algorithms that are explicitly written to access disk. Some of the more popular models are the two-level external memory model, the parallel disk model, and the cache-oblivious model. There are also hierarchical memory models. Algorithms and Data Structures for External Memory particularly chapter 2 describes the parallel disk model in detail, briefly describes other external memory models, and provides pointers into the literature. Some of these ideas and results go back about half a century.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I appreciate your answer, but why it is that, memory reads generally miss the analysis of algorithms? I suppose, generally, memory reads should factor in, as the memory reads should be atleast 'n' where 'n' is the input size. $\endgroup$
    – amsquareb
    Aug 1, 2017 at 17:51
  • $\begingroup$ @DerekElkins: You're right about the equality comparison; I'll delete my comment. I fully agree with the rest of your comment, and thus remain confused about what exactly is confusing the OP. $\endgroup$
    – j_random_hacker
    Aug 1, 2017 at 20:21
  • 1
    $\begingroup$ @amsquareb Getting the first item of a list does not require reading in the whole list. In "in-memory" models of computation, there is no such thing as a memory "read". Operations directly refer to "memory". We could imagine an operation internally involves loading some temporary registers with its inputs. If we did, then as long as number of inputs any operation is less than some fixed constant, the number of loads is at most a constant factor greater than the number of operations, and thus the asymptotic complexity is unaffected. This is the thrust of the answers to your other question. $\endgroup$
    – Derek Elkins left SE
    Aug 1, 2017 at 20:37
  • $\begingroup$ @DerekElkins Thanks a lot! Its now clear to me. Can you please incorporate above comment into your answer? $\endgroup$
    – amsquareb
    Aug 2, 2017 at 8:03

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.