1
The fundamental idea We use Big O notation which describes
the upper bound the worst-case scenario of how the runtime
increases.
Guideline 1: Single Loops
● Think about a simple for loop running from 1 to n. Inside that loop, you have
a statement.
● How many times does that statement run The answer is n times once for
each iteration of the loop.
● If that statement takes a constant amount of time to execute were ignoring
loop conditions and initializations for now, then the total time complexity is
On.
Lets put it in code:
python def processitemsn: for i in range1, n + 1: # Some constant-time operation
here printfProcessing item i
, 2
As n doubles, the number of times the loop runs and the time taken roughly
doubles. This is linear growth.
Guideline 2: Nested Loops - The Power of Multiplication
● This is where things get a little trickier. What happens when you have a loop
within another loop This is called a nested loop.
● Lets say you have an outer loop that runs n times, and an inner loop that also
runs n times for each iteration of the outer loop.
● Imagine this visually: for each i in the outer loop 1, 2, 3...n, the inner loop
does a full cycle 1, 2, 3...n.
● So, the statement inside the inner loop executes n * n = n times. Thats a
significant jump from just n We express this as On. This is quadratic growth.
Heres a code example to illustrate:
python def processpairsn: for i in range1, n + 1: for j in range1, n + 1: # Some
constant-time operation here printfProcessing pair i, j
The fundamental idea We use Big O notation which describes
the upper bound the worst-case scenario of how the runtime
increases.
Guideline 1: Single Loops
● Think about a simple for loop running from 1 to n. Inside that loop, you have
a statement.
● How many times does that statement run The answer is n times once for
each iteration of the loop.
● If that statement takes a constant amount of time to execute were ignoring
loop conditions and initializations for now, then the total time complexity is
On.
Lets put it in code:
python def processitemsn: for i in range1, n + 1: # Some constant-time operation
here printfProcessing item i
, 2
As n doubles, the number of times the loop runs and the time taken roughly
doubles. This is linear growth.
Guideline 2: Nested Loops - The Power of Multiplication
● This is where things get a little trickier. What happens when you have a loop
within another loop This is called a nested loop.
● Lets say you have an outer loop that runs n times, and an inner loop that also
runs n times for each iteration of the outer loop.
● Imagine this visually: for each i in the outer loop 1, 2, 3...n, the inner loop
does a full cycle 1, 2, 3...n.
● So, the statement inside the inner loop executes n * n = n times. Thats a
significant jump from just n We express this as On. This is quadratic growth.
Heres a code example to illustrate:
python def processpairsn: for i in range1, n + 1: for j in range1, n + 1: # Some
constant-time operation here printfProcessing pair i, j
