complexity

Why:

• Complexity is a way to compare execution time efficiency of different algorithm and/or different data structure.

• The efficiency index is measured ONLY by the number of objects under consideration. The efficiency index is represented by the Big O notation: O(1), O(log n), O(n), O(n log n), O(n**2), etc. whereas n is the number of objects.

Examples:

• • If an algorithm takes "constant" time to execute (regardless of how many objects), it is a "constant complexity", noted as O(1).

  • For example, print 5th object in an array, cout << A[4];

  • Another O(1) example: add an object to the end of array A;

  • If an algorithm's execution time is proportional to the number of objects, the algorithm has O(n).

  • For example, print all objects in an array, for (i=0; i<n; i++) cout << A[i];

  • Another O(n) example: find the largest object in a random array, write the code yourself :-)

• Note that complexity is not measured in real computer execution time (in seconds) nor storage space used. For example, printing first half of an array is going to have the same complexity as printing the whole array because it is determined by n. Half of n depends on n. Consequently, there is no such thing as O(n/2). O(n/2) is O(n). Same thing for printing twice: O(2n) is the same as O(n).

Comparing data structure and/or algorithm.