Page tree
Skip to end of metadata
Go to start of metadata

Computational Complexity

On an application level, speech processing algorithms usually are used in low-resource devices like mobile phones. Mobile devices have limited computational capabilities and, in order to preserve their battery, it is important to design efficient algorithms for them. There are multiple ways of analyzing the computational complexity of an algorithm depending on the stage of the design process or the purpose of the final application:


Big-O notation:


The complexity of an algorithm is usually understood as a measurement of the time that an algorithm would take to complete, given an input of size n. When the size of the input grows, the computing time should remain within a practical bound. For this reason, complexity is measured asymptotically as n approaches infinity. The most popular representation of algorithmic complexity is the Big-O notation. The Big-O notation gives an upper bound to the growth of the computing time of an algorithm. This proves especially useful, because this notation allows us to compare algorithms in worst case scenarios. Figure 1 shows the growth rate of different Big-O notations with respect to the input size.

For example, a complexity of O(n), read as "O n complexity', represents an algorithm whose computation time grows linearly with the input size. Some examples of every type of complexity are:


  • O(1) - The computation time does not grow with the size of the input:
    • Accessing an array index (a = array[4]).

  • O(log n) - The computation time grows with the logarithm of the input size:
    • Binary Search algorithms.

  • O(n) - The computation time grows linearly with the input size:
    • Traversing an array.
    • Comparing two strings.

  • O(n2) - The computation time grows with the square of the input size:
    • Matrix operations like traversing a 2D array or multiplying a 1D array with a 2D matrix.
    • Conventional Discrete Fourier Transform (Matrix multiplication).

  • O(n log n) - The "log n" term is added when O(n2) algorithms are performed with Divide and Conquer techniques to increase their efficiency.
    • Fast Fourier Transform.

  • O(2n) - The computation time doubles with each addition to the input data, therefore it grows exponentially:
    • Recursive algorithms → To solve a problem of size N, it is necessary to solve two problems of size N - 1.

  • O(n!) - Factorial growth represents algorithms that grow even faster than exponential examples:
    • Finding all the possible permutations of a list.



Weighted Million Operations Per Second (WMOPS),   ITU-T. Software tool library: User’s manual, 2009 


The Big-O notations gives us an intuitive idea of the complexity of specific algorithms. This allows us to compare which algorithm to use and choose the most efficient option. However, in applications like speech coding, it is important to know the exact number of operations that the system needs to perform in order to process each frame of audio.

The ITU-T provides guidelines to measure the number of operations in a program. This measurement takes into account that not all the operations have the same computational load and scales their values accordingly. For example, a logarithm is a much heavier operation than an addition. The final result is represented as Weighed Million Operations Per Second (WMOPS). Table 1 shows the weights used for each specific operation carried out.





Big-O notations

Figure 1: Evolution of computation time for multiple Big-O notations dependint on the input size.


























OperationExampleWeight
Addition a = b + c 1
Multiplication a = b c 1
Multiplication + addition a+ = b c 1
Move a = b 1
Store in array a[i] = b[i] + c[i] 1
Logical AND, OR, etc. 1
Shift a = b >> c 1
Branch if, if...else 4
Division a = b/c 18
Square-root a = sqrt(b) 10
Transcendental sine, arctan, etc. 25
Function call a = func(b, c, d)2 + number of arguments
passed and
returned
Loop initialization for(i=0;i<n;i++) 3
Indirect addressing a = b.c 2
Pointer initialization a[i] 1
Exponential pow, en 25
Logarithm log 25
Conditional test used in conjunction with
BRANCH
2

Table 1: Operations accounted by the WMOPS tool and their relative weight.

  • No labels