I’m confused checking the time complexity for the region constraints part. In the book it is written as O(n^2/(√(n)^2 x (√(n)^2)).
- The outside loop from I up to regionSize = √n
- The inner loop from J to regionSize = √n
- The inner loop accesses hasDuplicate which costs n to run.
so why is it written has O(n^2/√n^2 x √n^2? espcially the n√2/√n^2 part?
I think it’s written as √n√nn for a total time of O(n^2).
Would appreciate clarification. Thanks!