What is the average algorithmic complexity? Can you explain and give examples of algorithms with different complexities?

The average (amortized) algorithmic complexity is an estimate of the running time of an algorithm, averaged over all possible inputs or over a sequence of operations. It shows how many resources (time, memory) the algorithm will require on average, rather than in the worst or best case.

Examples of algorithms with different complexities:

• O(1) — constant time. For example, accessing an array element by index.
• O(log n) — logarithmic time. For example, binary search in a sorted array.
• O(n) — linear time. For example, searching for an element in an unsorted array.
• O(n log n) — for example, quicksort in the average case.
• O(n²) — quadratic time. For example, bubble sort.

An example of amortized complexity:

In a data structure called "dynamic array" (for example, slice in Go or ArrayList in Java), the operation of adding an element is usually O(1), but when the array overflows, memory is reallocated and elements are copied, which takes O(n). The amortized complexity of adding remains O(1), as reallocation happens rarely.

// Example of amortized complexity of adding to ArrayList
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add(i); // usually O(1), sometimes O(n) during resizing
}

Thus, the average complexity helps understand the actual performance of an algorithm under typical conditions.