Definition
1. Size of the problem – It is small enough to fit in the main memory of a
computer.
2. Worse Case complexity – If for a given size the complexity is taken as the
maximum complexity over all inputs of that size, the complexity is called
the worst-case complexity.
3. Expected complexity – If the complexity is taken as the average complexity
over all inputs of given size, then the complexity is called the expected
complexity.
4. Time Complexity - The time needed by an algorithm expressed as a function
of the size of a problem is called the time complexity of the algorithm.
5. Space Complexity – The space complexity is determined by the integers
stored in registers.
6. Asymptotic Time complexity – The limiting behavior of the complexity as
size increases is called the asymptotic time complexity.
7. Accumulator – All computation takes place in the first register r o called the
accumulator.
8. Bitwise Computation – There is a simple modification of the straight-line
program model which reflects the logarithmic cost function. The model,
which is called bitwise computation, is same as straight-line program. All
variables are assumed to have the values 0 or 1. The operations and, or,
exclusive or and not are used.
9. Decision Tree – The usual representation for a program of branches is a
binary tree called a decision tree.
[Link] of the tree – The time complexity of a decision tree is the height of
the tree as a function of the size of the problem.
Short Notes
(1) Random Access Machine Model (RAM)
- A Random-Access machine Model (RAM) is a one accumulator computer
in which instructions are not permitted to modify themselves.
- RAM consists of
(i) read-only input tape
(ii) write-only output tape
(iii) memory
(iv) program
- A RAM program is not stored in memory of the RAM, the program cannot
modify itself.
(2) RASP
- A RAM program is not stored in the memory of the ·RAM. the program
cannot modify itself.
- We now consider another model of a computer is called a random-access
stored program machine (RASP), which is similar to a RAM with the
exception that the program is in memory and can modify itself.
- The overall structure of a RASP is also similar to that of a RAM. But the
program of a RASP is assumed to be in the registers of the memory.
- Each RASP instruction occupies two consecutive memory registers.
- The first register holds an encoding of the operation code: the second
register holds the address.
- If the address is of the form =i, then the first register will also encode the
fact that the operand is a literal. and the second register will contain
- Integers are used to encode the instructions.
r
(3) Multitape Turing Machine (TM)
- It consists of some number k of types, which are infinite to the right.
- Each tape is marked off into cells, each of which holds one of a finite
number of tape symbols.
- One cell on each tape is scanned by a tape head, which can read and
write.
- Operation of the Turing machine is determined by a primitive program
called a finite control.
- The finite control is always in one of a finite number of states, which can
be regards as position in a program.
-
- Figure: A Multitape Turing Machine