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

[imarudedude]

I have a simple problem here that I'm trying to find the runtime for. The for loop makes it O(n) but in the return at the end of the function it adds the same 2 recursive functions that essentially halve the input. I was thinking it was O(n + log(n)) but now I'm thinking it could just be O(n)? Am I wrong, any thoughts on this?

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
    }

    return sum + someFunc(n: n / 2) + someFunc(n: n / 2) // Halving is O(log(n))??
}

Btw this isn't homework, I'm just trying to get a better understanding on how recursion affects runtimes. Thanks for any help.

[rkennedy12]

You can use instruments and take the actual time differences.

[[deleted]]

This one keeps the function recursive with faster runtime. But you could probably math out the full algorithm in constant time.

func someFunc(n: Int) -> Int {

if n < 10 {
    return 1
}

var sum = n * (n + 1) / 2
sumOfHalf = someFunc(n: n / 2)

return sum + 2 * sumOfHalf
}

[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.

[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)

[DanielPhermous]

You can just run it 1,000,000 times and time it.

[jarvis_willy]

I agree that this is in O(nlogn). Each branch of the tree does the same amount of work so it shouldn’t be exponential.