functional-programmingtime-complexity# What is the time complexity of this? It uses 3 loops and the innermost loop depends on the outermost?

```
function fun(N) {
let k = 0;
for(let i = N; i >= 1; i = i/2) {
for (let g = 1; g <= N/i;g = g + 1) {
for (let h =1; h <= i;h = h + 1) {
k = k + 1;
}
}
}
return k;
}
```

My analysis of the given problem is as follows:

The outer loop runs until `i`

becomes less than **1**, and in each iteration, `i`

is divided by **2**. This implies that the outer loop will run logarithmically in base **2** with respect to `N`

. Specifically, the outer loop will run until `i`

becomes less than **1**, and the number of iterations can be expressed as `log₂(N)`

.

The middle loop runs for `N/i`

times, where `i`

is the control variable of the outer loop. Therefore, the middle loop contributes a factor of `N`

to the time complexity.

The innermost loop runs `i`

times, and is dependent on the outer loop. Thus we do not consider its time complexity.

Therefore, overall time complexity of the function is `O(N log N)`

, is it right?

Solution

Your answer of a time complexity of `O(N log N)`

is correct, but your derivation is not.

Consider the inner two loops involving `g`

and `h`

. The innermost loop with index `h`

runs `i`

times, thus having complexity `O(i)`

. The loop with index `j`

runs `N/i`

times, thus having complexit `O(N/i)`

. As these two loops are nested, the total complexity is `O(i) * O(N/i) = O(N)`

. Therefore, the time complexity of the inner two loops is independent of `i`

and is always `O(N)`

.

The outermost loop with index `i`

runs `O(log N)`

times, and your logic behind this is correct.

Thus, the total time complexity of all three loops is `O(log N) * O(N)`

, giving an answer of `O(N log N)`

.

- Why doesn't contravariance apply in certain cases like [b] → Int < a → Int
- Does JavaScript have a method like "range()" to generate a range within the supplied bounds?
- How can I make a functional chaining operator in Raku?
- Is there a PHP equivalent of JavaScript's Array.prototype.some() function
- Why is the Factory pattern not needed in Haskell? And how are the needs that pattern addresses in OOP addressed in Haskell?
- Python: Haskell-like . / $
- how to do Seq.takeWhile + one item in F#
- Returning `nil` from a `compactMap()` closure fails result type check
- What is it called and what does it mean when a function "equals" another function and provides a body?
- Can you explain closures (as they relate to Python)?
- Is there a way to 'restrict' elm function f : A -> Maybe B into f0 : ProperA -> B without using Debug.todo?
- When can a pointful function be refactored to be point free?
- Why is it done in std::ranges that I can't split the range that I got from join with transform
- Is environment model necessary for higher-order procedures?
- Compile to xslt?
- Using ML in "Real-World" Applications
- Functional pipes in python like %>% from R's magrittr
- Is there something like the threading macro from Clojure in Python?
- What is the difference between functions and data?
- Optimization of tail recursion in R
- Python method chaining in functional programming style
- trace a nested recursion in Ocaml
- Haskell Linked-List Monad
- How can I map a String to a function in Java?
- Tail recursion on R Statistical Environment
- What is the way to chain methods with different signatures describing a business process?
- How to properly propagate an error through non-error function?
- Groovy: what is analogue for java stream anyMatch
- Dart: mapping a list (list.map)
- Is there a Functional Programming library for .NET?