The doSomething() calls always make me chuckle. Hours into a debug: PleaseWork(), doSomething(), whyAreYouLikeThis() haha
5 months ago (edited) | 5
I like how everyone except top right are doSomething. So I guess the general idea is, you also have to look at how input is processed. And n^2 usually re processing the same (or almost the same) number of input?
5 months ago | 3
Your image has one big problem. It didn't outline which code snippet is 1 2 3 or 4
5 months ago | 0
NeetCodeIO
A Nested Loop Is Not Always O(n²)!
Most people mistakenly 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/
5 months ago | [YT] | 543