when youโre not writing triple or quadruple nested loops, then are you really even coding?
8 months ago | 38
Yes. Many two pointers algorithms use nested for loops and are O(n). In general, if you are keeping track of two monotonically increasing pointers (or indexes) in the two for loops, the time complexity should be O(n).
8 months ago | 10
I also was surprised when Iโve seen a nested while loops with O(n) in sliding window approach Pretty hard to understand at first glance
8 months ago | 6
For (int I=0, I<5:I++) For(int j=0:j <5;j++) Printf("*") O(1): tadaaa
8 months ago | 0
NeetCode
A Nested Loop Is Not Always O(nยฒ)!
(Don't make this mistake)
Most people assume a nested loop runs in quadratic time.
But this is not always the case. For it to run in quadratic time, there are specific requirements, and actually, it might even have a different complexity!
Take a look at four examples (left to right):
1) The inner loop runs n times on each iteration of the outer loop, which evaluates O(nยฒ). This is the simplest and a common case you've probably encountered.
2) In the sliding window algorithm, the outer for loop runs ๐ฒ๐ ๐ฎ๐ฐ๐๐น๐ n times, where n = arr.size(), and the while loop can run ๐ฎ๐ ๐บ๐ผ๐๐ n times in total, meaning if it executed n times for one iteration, it won't run at all for other iterations. - O(n). This is also known as amortized analysis.
3) The outer loop runs from i = 0 to i < n, while the inner loop runs from j = i to j < n, meaning for each i, it executes (n - i). If we expand this summation, the leading term becomes O(nยฒ) .
4) The inner loop multiples j by 2 at each iteration, meaning it follows the sequence 1, 2, 4, 8, 16. The number of iterations is:
j = 2^k โค n, which is k = logโn <-- by the definition of the logarithm.
This means that the inner loop runs log n times, which is why the nested loops run in O(n log n) time.
---
๐ Join over a million people preparing for coding interviews -> neetcode.io/
8 months ago | [YT] | 961