Chapter 13 Flashcards
activation record
An area of computer memory that keeps track of a method call’s parameters, local values, return value, and the caller’s return address. (493)
big-O notation
A formal notation used to express the amount of work done by an algorithm or the amount of memory used by an algorithm. (502)
binary search algorithm
The process of examining a middle value of a sorted array to see which half contains the value in question and halving until the value is located. (509)
call stack
A large storage area created at program startup. (493)
complexity analysis:
For algorithms, the process of deriving a formula that expresses the rate of growth of work or memory as a function of the size of the data or problem that it solves. (502)
infinite recursion
A situation that occurs when the run of a recursive algorithm reaches no stopping state. (492)
iterative process
A process that repeats with no growth of computer memory. (501)
quicksort
A sorting technique that moves elements around a pivot recursively and sorts the elements to the left and the right of the pivot. (512)
recursive method
A method that calls itself. (491)
recursive step
A step in the recursive process that solves a similar problem of smaller size and eventually leads to a termination of the process. (492)
stack
A dynamic data structure in which access can be made from only one end. Referred to as a LIFO (last-in, first-out) structure. (516)
stack overflow error
A situation that occurs when the computer runs out of memory to allocate for its call stack. This situation usually arises during an infinite recursion. (492)
stopping state
The well-defined termination of a recursive process. (492)
tail-recursive
The property that a recursive algorithm has of performing no work after each recursive step. (501)
