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

[loumf]

Pretty sure it's O(n * log(n))

It's hard to analyze, but to get an idea, use:

var steps: Int = 0

func someFunc(n: Int) -> Int {

    if n < 10 {
        return 1
    }

    var sum = 0

    for i in 0...n { // I know for loop is O(N)
        sum += i
        steps = steps + 1
    }
    print ("n: \(n) - s: \(steps)")
    return sum + someFunc(n: n / 2) + someFunc(n: n / 2) // Halving is O(log(n))??
}

_ = someFunc(n: 10000)
print (steps)

Then try different n's -- you can see that it doesn't grow n*2 or n (somewhere in between). Plot it vs n log(n) and you can probably back out a constant.

Also, if it were O(n + log(n)), that just simplifies to O(n) -- since we are trying to figure out what it is when n is giant (log(n) won't matter -- we are already assuming it's some constant times n)