CISC 235 Lecture Notes - Lecture 2: Random-Access Machine, Complex Instruction Set Computing, Time Complexity

61 views6 pages

Document Summary

We will prefer structure a to structure b if a has a lower order of complexity for the operations we need in our particular application. clarify which operations can be completed in constant time. Before we discuss computational complexity, we need to agree on the type of computer we are dealing with. We will use the random access machine model, which can be summarized as follows: Sequential operations only (i. e. no parallel computation) +, -, *, / and comparisons for integers and floating point numbers. Assigning a value to a variable take constant time. No hardware accelerators (such as caches or virtual memory) are employed. It is important to note that this model implies an upper limit on the number of digits in any number. This is true of virtually all programming languages. The ram model does not assume constant time operations on strings. A string is considered to be a data structure consisting of a sequence of characters.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents

Related Questions