1Basic Notions on Computational Complexity and Approximate Techniques

1.1. Computational complexity

1.1.1. Introduction

The execution time of a program depends on several factors:

  • – program data: for example, sorting about 10 numbers requires less execution time than sorting out millions of numbers;
  • – quality of the code generated by the compiler: codes generated by programming languages do not all have the same quality (this is the case of C, C++ and Java: if the application is not object-oriented and will be executed on some platform (operating system, processor frequency, memory size, etc.), then it is better to implement it in C, which generates a “lighter” code);
  • – computational complexity: this metric gives the developer an idea of the execution time of their program, independently of programming language and platform (processor, memory capacity, etc.). Computational complexity is therefore an important concept, all the more so as it offers the developer an indication on whether their program takes a reasonable CPU time to reach results, even when significant resources (processor frequency, memory capacity) are at their disposal. In other terms, it may signal to the designer the need to modify their algorithm, if it takes an “infinite” time to reach results.

1.1.2. Big O notation

DEFINITION.– Computational complexity T(n) is O(f(n)) if there are constants c and n0 such that: T(n) ≤ c * f(n) ∀ n ≥ n0; c > 0; n0 ≥ 0

EXAMPLE 1.1.– T(n) = (n+1)2

T(n) is O(n2). Indeed, ...

Get CAD of Circuits and Integrated Systems now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.