Series Intro:
This series contains notes from interviewcake full couse of Data Structures and Algorithms.
Big O Notation
Using not-boring math to measure code's efficiency
What is Big O Notation
Big O notation is the language we use for talking about how long an algorithm takes to run. It's how we compare the efficiency of different approaches to a problem.
With big O notation we express the runtime in terms of—brace yourself—how quickly it grows relative to the input, as the input gets arbitrarily large.
Breakdown of Big O Notation
How quickly the runtime grows
It's hard to pin down the exact runtime of an algorithm. It depends on the speed of the processor. We use big O notation to talk about how quickly the runtime grows.
Relative to the input
If we were measuring our runtime directly, we could express our speed in seconds. Since we're measuring how quickly our runtime grows, we need to express our speed in terms of...something else. With Big O notation, we use the size of the input, which we call "nn." So we can say things like the runtime grows "on the order of the size of the input".
As the input gets arbitrarily large
Our algorithm may have steps that seem expensive when nn is small but are eclipsed eventually by other steps as nn gets huge. For big O analysis, we care most about the stuff that grows fastest as the input grows, because everything else is quickly eclipsed gets very large.
SOOOO LONG PARAGRAPHS. Right?
Lets take a break here.
Will continue in next blog...
Thanks for reading <3
Top comments (0)