C DSALesson 65Free preview

C Big O

This lesson is part of C · All levels

Summary

Big O Notation describes the worst growth in time or space of an algorithm as the size of the input increases, without affecting the speed of the computer. Common notations are constant, logarithmic, linear, and quadratic. By comparing complexity, you can pick the right algorithm before the size of the data becomes a problem.

Key points

Focus on the order of growth; constants and subset are ignored, for example 2n^2 + 100n becomes O(n^2).
The access array is O(1), linear search O(n), binary search O(log n), and nested loop O(n^2).
The complexity of the worst case and the average case can vary, for example the quicksort being the average.
Space complexity is also important, for example, in-room recursion using multiple stack frames.
Comparing O(n log n) to O(n^2) shows how big the impact is choosing the right algorithm.

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.