Time Complexity Analysis of Loops
Loop with Multiplying Counter (Logarithmic)
When a loop's counter variable is multiplied by a constant each iteration, it executes logarithmically.
Example: I = I * 2
for (i = 1; i < n; i = i * 2) {
// statement
}
Analysis:
- I starts at 1, then becomes: 1, 2, 4, 8, 16, ... (powers of 2)
- After k iterations: I = 2^k
- Loop terminates when I ≥ n, so 2^k = n
- Therefore, k = log₂ n
Time Complexity: O(log n)
Handling Non-Exact Powers
- If n = 8: log₂ 8 = 3 (exact), loop runs 3 times
- If n = 10: log₂ 10 ≈ 3.32, loop runs 4 times (ceiling of log)
- Always take the ceiling (round up) when dealing with non-exact powers
General Formula for Multiplication
- Multiplication by 2: O(log₂ n)
- Multiplication by 3: O(log₃ n)
- All log bases are O(log n) in Big-O notation
Loop with Dividing Counter (Logarithmic)
When a loop starts at n and divides by a constant each iteration:
Example: I = I / 2
for (i = n; i >= 1; i = i / 2) {
// statement
}
Analysis:
- I starts at n, then becomes: n, n/2, n/4, n/8, ...
- After k iterations: I = n / 2^k
- Loop terminates when I < 1, so n / 2^k = 1
- Therefore, 2^k = n, k = log₂ n
Time Complexity: O(log n)
Loop with Incrementing Counter (Linear)
Standard Increment (I++)
for (i = 1; i <= n; i++) {
// statement
}
Analysis:
- After k iterations: i = k
- Loop terminates when i > n, so k = n
Time Complexity: O(n)
Increment by Constant
- i = i + 2: O(n)
- i = i + 10: O(n)
- Any constant increment/decrement is O(n)
Loop with Square Condition (Square Root)
Example: I * I <= N
for (i = 1; i * i <= n; i++) {
// statement
}
Analysis:
- Loop runs while i² ≤ n
- Terminates when i² = n
- Therefore, i = √n
Time Complexity: O(√n)
Independent Loops (Additive)
Two Independent Linear Loops
for (i = 0; i < n; i++) { /* O(n) */ }
for (j = 0; j < n; j++) { /* O(n) */ }
Analysis:
- Total operations: n + n = 2n
Time Complexity: O(n) (not O(n²) since loops are not nested)
Dependent Independent Loops
p = 0
for (i = 1; i < n; i = i * 2) { p++ } // O(log n)
for (j = 1; j < p; j = j * 2) { /* statement */ } // O(log p)
Analysis:
- First loop: p takes value log n
- Second loop: repeats log p times = log(log n) times
Time Complexity: O(log log n)
Nested Loops (Multiplicative)
Linear Outer × Logarithmic Inner
for (i = 0; i < n; i++) { // O(n)
for (j = 1; j < n; j = j * 2) { // O(log n)
// statement
}
}
Analysis:
- Outer loop: n iterations
- Inner loop: log n iterations per outer iteration
- Total: n · log n
Time Complexity: O(n log n)
Summary of Loop Time Complexities
| Loop Pattern | Time Complexity | |-------------|-----------------| | i++ (increment by 1) | O(n) | | i += constant | O(n) | | i-- (decrement by 1) | O(n) | | i -= constant | O(n) | | i = i * 2 | O(log₂ n) | | i = i * 3 | O(log₃ n) | | i = i / 2 | O(log₂ n) | | i * i ≤ n | O(√n) |
Key Takeaways:
- Multiplying or dividing the counter → Logarithmic time
- Incrementing or decrementing by constant → Linear time
- Nested loops multiply complexities
- Independent loops add complexities
- Ceiling of log is used for non-exact powers
For a deeper understanding of how these loop patterns fit into the broader picture of algorithmic analysis, explore our guide on How to Write and Analyze Algorithms: Time and Space Criteria. To master the foundational concepts behind these complexities, read about Understanding Time and Space Complexity: A Comprehensive Guide to Big O Notation. If you want to practice analyzing nested loops like the multiplicative pattern above, see How to Analyze Time Complexity of Nested Loops and Sequences. For a systematic method to compute these complexities, refer to Algorithm Complexity: Frequency Count Method for Time Space Analysis. Finally, to build your intuition from the ground up, check out Time & Space Complexity Basics: Big O Notation Explained for DSA.
next I have this piece of code I have to analyze and find the time complexity of this one and this code also for Loop is
used but Loop is starting from one going up to n that is less than n and it is being multiplied by two I is multiplied
by two every time so blindly we cannot say this will execute for n times we have to analyze this one let us see how
many times this will execute it's not n we don't know how many times let us see I will take
the I value initially it is one the next time it's going to be 1 into 2 that's is 2 the next time it will be 2 into 2
again so it will be 2 squ see every time it's getting multiplied by 2 then it's 2 s into 2 again so this will be 2^ 3 goes
on how many times that we don't know so let us say this will execute for 2 power K
times 2 pi K times now we know that this will terminate when I
becomes greater than equal to n so we assume that when it has reached for some K number of times it has repeated
assume I became greater than equal to n and what is our I value 2^ k since I = to 2 power K
therefore 2 power K has became greater than equal to n now if I take 2^ K is equal to n then K is how much log n base
2 yes this is the time complexity so the statement will execute for order of log and base 2 times
so from this we can observe that if you have a loop where the counter variable it's not incrementing but it's getting
multiplied by something let us say two or three then it will get log base 2 time so it will execute for log base 2
times now I have a incremental F Loop here the regular Loop that we use let us analyze that one and then we will
analyze once again here the other method I will show you see here I is initially one and it is incrementing by one + one
then + one then + one goes on + one and it will stop when finally it becomes greater than n so up to n so how many
times is getting added so let us say k times and that is equal to n so how many times K times what is that K it's equal
to n now let's take this one I is initially one then it is next time into two then again into two then again
into two so up to sometimes so finally it will stop when it becomes greater than equal to
n then this is how many times so this will be let us say k time so what will be the result this will be 2 K that will
be equal to n so K is how much log in base 2 so the other way have this one so that is incrementing one one
one so K time so this is multiplying by 2 2 2 every time so K times is getting multiply it so it's 2^ K that is equal
to n so K is how many times K is log n base 2 time so if you have any Loop like this the value of I is getting
multiplied then it is going to take log and time so you can take it as a formula now the time complex taken by this
algorithm is log n the statement will repeat for log
times now when you take log n log n may give decimal values float values so we need to know whether I have we have to
take floor or seal of that value so that is important means should we truncate it or round up the value so for that let us
take some example and check it suppose n value is 8 right now I value let us start trace
this one by taking a sample value I is 1 initially then I is multiplied by 2 so it is 2 2 is less than 8 2 is less than
8 then again multip by 2 4 so 4 is less than 8 n is 8 right so again multiplied by 2 now 8 is not less than 8 so it will
stop so total how many times it is repeating it is repeating for three times the next if I take the N value as
10 if I write the N value as 10 let us see what happens I is initially 1 1 is less
than 10 now n value is a 10 1 is less than 10 continue it's multiplied by 2 so 2 is less than 10 4 4 is less than 10 8
multip by 2 it is 8 8 is also less than 10 then 16 so 16 is I I is not less than 10 so it will stop here so total how
many times four times it's executing for four times if I find log 8 log 8 will be 3 how log 8 is
written as 2^ 3 base 2 and it is written as 3 log 2 base 2 and this is 1 so answer is three now same way if I find
out log 10 base 2 now 10 is not an exact powers of two so I will not get the decimal value integer value I may get a
decimal value right so let us take it as example 3.2 I'm assuming it as 3.2 I got 3.2 but if you see the number of times
repeated four times so it should be taken as seal value so this log should be taken as
seal when you use log sometimes whether it is Seal or floor that is also important right another piece of code
here let us see how it's going to execute what will be the time complexity of this one see here I is starting from
n and next time I value is n by 2 the next time is n by 2 s then n by 2 Q so on how many times n by 2^ K we don't
know the number of times so we are assuming it as for K times and we know that the loop will terminate when I
becomes less than 1 so it will continue as long as greater than equal to 1 so assume I has
became less than 1 so therefore what is I value 2^ K is less than 1 so if I equate
it then it's going to be 1 and N is = 2^ K so K is how much log n base 2 so again the time for this one is order of log n
base 2 so the time complexity of this piece of code is also log n base 2 so the
previous one and fifth example I have shown you that it was multiplying every time and starting from one now this is
dividing every time it starting from n n and up to what up to one it is reaching so it's order of log n next piece of qu
is the seventh example I'm taking here so here I is starting from Z I into I is less than equal to n so how
many times this will execute this is Will execute as long as I into I is less than
n but it will terminate when I into I is greater than equal to n we assume that I into I is i² is equal to n so what is I
it's Ro 10 so I don't have to K here I have not used K here directly using I only I have shown you I T less than n
min this is a square if you send that side it's a root so it will execute for root n times now the next example here I
have two follow Loops these are independent Loops one after another don't mistake it as nested Loop
they are not one inside another so the time complexity for this one is this is independent Loop and it is iterating for
n times and it's incremental Loop so it's order of n and this is also incremental Loop this is also order of n
so if you combine them and take their time that is 2 + 2 so n + n that is 2 N and it is order of
n so this are independent loop at the time is order of n Only n+ n that is order of n it's not n² now next
one I have two Loops here independent Loops this next loop I have to find out what is the time taken by this statement
if I observe only this one then J is taking values from one J is less than n j is incrementing that is updating by
multiplied by two every time so this is going to take log value log of what log of P so this is log
P what is a p if you see the previous Loop here p is incremented so p is incremented in this Loop so so this P
will take the value that number of times this Loop is repeating how many times this Loop is repeating I takes the
values 1 one 2 N and I assign I into 2 so again it is log log of what it is log n so P value will be log n and this
statement will repeat for log P time so what is p p is evaluated here and it is used here right so this is log of log
n as p is equal to log n so it is log of log n so the time complexity is order of log of log n next example here I have
nested for Loop the outer loop is taking I sign 0 I is less than n and I is incrementing so this is order of n as
this is a increment Loop so this is order of N and whatever is there inside will repeat for n times
next the inall Lo this is using J J is less than n and J is every time multiplied by 2 right so this will take
log and time so this itself will take log and time and anything inside that also will
take log in time if you remember initially I I have shown you that this is this takes n + 1 no it will not be
any uh useful if you write n + one or don't write it makes no difference just you can take it as n now total how much
2 N log n + n so highest term is this one so this is order of n log n so the time
complexity of this one is order of analog in now let us write some pieces of code and see what the time
complexities that we have got so far see if I write a for Loop for I I assign 0 I is less than n i ++ for this we got the
time as order of n this is incrementing Loop if this is written as I assign 0 I is less than n and I assign I + 2 this
is going to be n by 2 that also we take order of n then
for I assign n i is greater than 1 i - minor this also order of n so if it is
incrementing also order of n if it is decrementing also order of n then for I assign 1 I less than N I assign I
multiped by 2 this is order of log n base 2 so it means for I assign 1 I is less than N I assign I into 3 this will
be order of log n base 3 for I assign n i is greater than 1 and I assign I by 2 it's order
of login base 2 so now we can take these as formulas if a loop is incrementing that is n or
decrementing it is n whether it is incrementing by 1 or two or even 10 or even 100 also it's order
of n Only we say right n by2 is also order of n n by 200 is also order of
n because we are writing the degree of the polinomial that is n is the term used there the variable n is used for
order of n if n sare by 2 then we say n² right so this is a summary of the
time complexity we have seen
When a loop's counter is multiplied or divided by a constant each iteration, the time complexity is logarithmic. For example, a loop with i = i * 2 (or i = i / 2) has a time complexity of O(log n). This is because the number of iterations required for the loop to terminate is the power to which the constant must be raised to reach the condition value, such as log₂ n.
Nested loops multiply their complexities: if you have an O(n) outer loop and an O(log n) inner loop, the total time complexity is O(n log n). In contrast, independent (non-nested) loops add their complexities: two independent O(n) loops result in an overall time complexity of O(n) since 2n is simplified to O(n) in Big-O notation.
If a loop runs while i * i <= n, the loop terminates when i² = n, meaning the loop iterates for i = √n times. Therefore, the time complexity of this loop is O(√n). This is because the counter increments linearly, but the square condition limits the number of iterations to the square root of the input value.
A loop that divides the counter (e.g., i = i / 2) has a logarithmic time complexity of O(log n), similar to multiplication. Conversely, a loop that increments or decrements the counter by a constant (e.g., i++ or i = i + 10) has a linear time complexity of O(n). The key distinction is that division/multiplication changes the counter exponentially, reducing iterations, while constant changes keep the number of iterations proportional to n.
Even when incremented by a constant other than 1, like i = i + 2 or i = i + 10, the time complexity remains linear O(n). This is because the number of iterations is still proportional to n (e.g., n/2 or n/10 iterations), but in Big-O notation, constant factors are ignored, so the complexity is simply O(n).
When n is not an exact power of the multiplication constant (e.g., n = 10 for i = i * 2), use the ceiling of the logarithm. For instance, log₂ 10 ≈ 3.32, but the loop will run 4 iterations (the integer ceiling) to exceed the condition. In Big-O notation, the complexity is still O(log n) because constant factors and ceilings are ignored.
In dependent independent loops, the overall time complexity is determined by the inner loop's complexity based on the outer loop's result. For example, if the first loop calculates p = log n (O(log n)), and the second loop runs O(log p) times, the complexity becomes O(log log n). This is because the second loop's iterations grow at a much slower rate than the first.
Keep this summary
Save it to LunaNotes and it becomes a real note in your library — editable, searchable, and ready to turn into flashcards or a diagram. Free to start.
Save to LunaNotesOr summarise for another video.
32K+ people have turned 65K+ videos into notes
“Very useful tool. I'm using it for the last couple weeks and I'm loving it so far. Makes learning on YouTube a great experience.”
Bhai Chrome Web Store reviewThis summary and transcript were automatically generated using AI with the Free YouTube transcript summary tool by LunaNotes.
Related summaries
How to Analyze Time Complexity of Nested Loops and Sequences
This video teaches you how to calculate the time complexity of various loop structures in code, including simple loops, nested loops, and loops with non-standard increments or conditions. Through detailed tracing and analysis, you'll learn to identify Big O notation for O(n), O(n²), and O(√n) complexities, making algorithm analysis straightforward.
Understanding Time and Space Complexity: A Comprehensive Guide to Big O Notation
Explore the concepts of time complexity, space complexity, and Big O notation with practical examples.
Algorithm Complexity: Frequency Count Method for Time Space Analysis
Learn how to analyze algorithm efficiency using the frequency count method. This video demonstrates time and space complexity analysis for sum of array elements, matrix addition, and matrix multiplication algorithms.
Asymptotic Analysis Part 3: Growth Rates & Time Complexity
Learn why we use asymptotic complexity instead of exact running times in algorithm analysis. This tutorial explains how time complexity depends on input size and why higher-order terms dominate for large inputs, using clear examples with array shifts and growth rate calculations.
Time & Space Complexity Basics: Big O Notation Explained for DSA
This video introduces time complexity and space complexity concepts for coding interviews. The instructor explains why time taken is not time complexity, defines Big O notation, and covers the three key rules for computing complexity: worst-case scenario, avoiding constants, and ignoring lower-order terms. It also covers space complexity, auxiliary vs input space, and the crucial rule of not modifying input data.
Most viewed summaries
A Comprehensive Guide to Using Stable Diffusion Forge UI
Explore the Stable Diffusion Forge UI, customizable settings, models, and more to enhance your image generation experience.
Kolonyalismo at Imperyalismo: Ang Kasaysayan ng Pagsakop sa Pilipinas
Tuklasin ang kasaysayan ng kolonyalismo at imperyalismo sa Pilipinas sa pamamagitan ni Ferdinand Magellan.
Mastering Inpainting with Stable Diffusion: Fix Mistakes and Enhance Your Images
Learn to fix mistakes and enhance images with Stable Diffusion's inpainting features effectively.
Pamamaraan at Patakarang Kolonyal ng mga Espanyol sa Pilipinas
Tuklasin ang mga pamamaraan at patakaran ng mga Espanyol sa Pilipinas, at ang epekto nito sa mga Pilipino.
How to Install and Configure Forge: A New Stable Diffusion Web UI
Learn to install and configure the new Forge web UI for Stable Diffusion, with tips on models and settings.
Found this summary useful?
Take it with you. One click puts it in your own LunaNotes library.
Save to LunaNotes