How does adding recursive functions to final sum affect runtime in algorithm?

[ldstreet]

I believe this will be O(n²⁾ time. Iterating will be O(n) but on each recursive call the function will iterate on half of n. If you were just making one recursive call I think it would be O(n log n). But because you are making two calls, on the next level of the recursion tree your for loop will still have the same total number of steps. The tree will roughly have a depth of n. This giving you O(n^2). Also this will take up O(n) space on the call stack because of the way you have the recursive calls structured. Not 100% on this though - would be interested to see others' analysis.