In the worst case, we make as many operations/divisions as we can divide the array into two parts. For example, how many times can we divide an array of 4 elements into two parts? Twice. And an array of 8 elements? Three times. So, the number of divisions/operations = log2(n) (where n is the number of elements in the array).

Conclusions:

- Accessing an element of a collection is O(1). Whether it's accessing by index in an array or by key in a dictionary, in Big O notation this is O(1).

- Iterating over a collection is O(n).

- Nested loops over the same collection are O(n^2).

- Divide and Conquer algorithms are always O(log n).

- Iterations that use Divide and Conquer are O(n log n).

<< Prev | 11/11
English
Home