2.4 Constant time operations

Constant time operations

In practice, designing an efficient algorithm aims to lower the amount of time that an algorithm runs. However, a single algorithm can always execute more quickly on a faster processor. Therefore, the theoretical analysis of an algorithm describes runtime in terms of number of constant time operations, not nanoseconds. A constant time operation is an operation that, for a given processor, always operates in the same amount of time, regardless of input values.

Activity 1: Constant time operations.

  1. The statement below that assigns x with y is a constant time operation.
    imageq1
    True
    False


  2. A loop is never a constant time operation.
    True
    False


  3. The 3 constant time operations in the code below can collectively be considered 1 constant time operation.
    imageq3
    True
    False


Identifying constant time operations

The programming language being used, as well as the hardware running the code, both affect what is and what is not a constant time operation. Ex: Most modern processors perform arithmetic operations on integers and floating point values at a fixed rate that is unaffected by operand values. Part of the reason for this is that the floating point and integer values have a fixed size. The table below summarizes operations that are generally considered constant time operations.

image1

Activity 2: Identifying constant time operations.

  1. In the code below, suppose str1 is a pointer or reference to a string. The code only executes in constant time if the assignment copies the pointer/reference, and not all the characters in the string.
    imageq4
    True
    False


  2. Certain hardware may execute division more slowly than multiplication, but both may still be constant time operations.
    True
    False


  3. The hardware running the code is the only thing that affects what is and what is not a constant time operation.
    True
    False