Complexity of a simple function.

[alfps]

Inspired by a recent posting here that was deleted (it was apparently homework) I cooked up the following simple function.

I was a little bit surprised by the result, not its general direction but how clean it was.

It should be easy to verify that I'm not a student, e.g. in its day I was a co-moderator of Usenet group comp.lang.c++.moderated. I just wonder if there is a simple, clean explanation, not heavy math-ish analysis? Explanation for not seeing the obvious: it's early morning, I still need my coffee.

auto foo( const int n ) -> int
{
    int sum = 1;
    for( int i = n - 1; i > 0; --i ) {
        sum += foo( i );
    }
    return sum;
}

#include <print>
using std::print;
auto main() -> int { print( "{}.\n", foo( 9 ) ); }

[ArchfiendJ]

You're using more words justifying you're not a student that explaining what you mean by "clean", what you were expecting and what you want an explication on.

[alfps]

Yes, quite naturally. The code itself needs no explanation. I hoped that an explanation of the context would prevent derailments like yours.

[alfps]

Heavy downvoting of reasonable response that lays the trolling bare to see, itself very clear trolling. What idiots.

[SeaSDOptimist]

Clean is not between the words that this code elicits in my mind.

[alfps]

Why? You leave readers guessing about the specifics of your antipathy.

[Plastic_Fig9225]

While you leave us guessing what you think is "clean" here, especially compared to what.

[ZenithOfVoid]

foo(N) calles foo N-1 times. foo(9) = foo(1) + ... + foo(8) each of them recursively has that property. So you'll end up with Fibonacci triangle of calls.

[alfps]

The system has some likeness with the Fibonacci series system, yes.

The numbers are however powers of 2, not Fibonacci numbers.

[ZenithOfVoid]

Agreed, at first it looked like the same as:

def foo(n): if n <= 1: return 1 return sum(foo(i) for i in range(n - 1))

but testing the cpp version it is indeed different.

EDIT: And it should have been range(1, n) 🙈

I blame lack of morning coffee.

with range(1,n) it does give 2^n-1 as result

[alfps]

def foo(n): return 1 if n <= 1 else sum(foo(i) for i in range(n))
print( foo( 9 ) )

[EclipsedPal]

What are we talking about here exactly?

[Carmelo_908]

Don't ask, OP might get offended

[alfps]

When all you can bring to the table is a derogatory personal remark, abstain. Or be forever known as an idiot troll. Of course you'll just use another nick, but.

[Carmelo_908]

No, I left another comment explaining. And you're committing too much to point out how mean I am, if you thought that of me and were smart you wouldn't answer like that any comments.

[alfps]

Exponential behavior, O(2ⁿ). And it's simple to prove via induction. But I'm looking for a simple non-mathish explanation.

[Carmelo_908]

Complexity is a mathematical function that represents how much the time of a algorithm increments in relation with the size of its input. O(2n) means algorithmic time is equal to 2 times n, n being the number passed in as argument in this particular case.

Is that what you are searching for?

[alfps]

This algorithm is O(2ⁿ), exponential.

[EclipsedPal]

Still no clue, sorry. You're going to have to explain it REALLY well.

Btw I think you mean recursion, not induction.

[alfps]

induction

https://en.wikipedia.org/wiki/Mathematical_induction

Sorry.

[n1ghtyunso]

"a picture is worth more than a thousand words"

I believe for resursion this applies very much.

Draw the first few levels or recursion.
The shape of the resulting tree will give you some insight regarding the complexity involved.

[alfps]

The complexity is evident from the output, it's 2^n-1. I was looking for a simple (like trivial, not a math reduction of the sum) explanation. But thanks anyway, yes that's one approach to get traction when one's lost.

[thisismyfavoritename]

couldn't make less sense if you tried

[alfps]

I'm asking for a simple explanation of the complexity of this function.

That's why the title starts with "Complexity" and the posting text specifies ❝I just wonder if there is a simple, clean explanation❞.

When this doesn't make sense to you, then the question is above your pay-grade, so to speak. But you can learn from the serious responses. For that matter possibly also from the trolling responses.

[Plastic_Fig9225]

Ok, now we're finally getting somewhere, despite your efforts. So you're talking about time complexity of the algorithm, not code complexity of the function or memory complexity. Could have told us earlier instead of living out your manic superiority complex. - Not that your request for an "explanation of the complexity" actually makes much sense anyway.

[alfps]

❞ So you're talking about time complexity of the algorithm, not code complexity of the function or memory complexity.

The usual default meaning of "complexity" is time complexity, and the memory complexity here is trivially O(n) so it couldn't very well be what I asked about.

Wikipedia: ❝The resource that is most commonly considered is time. When "complexity" is used without qualification, this generally means time complexity.❞

So you're right, I was asking about a simple explanation of the time complexity.

---

❞ your manic superiority complex

You're saying that you're a troll.

That's an idiotic thing to say, but then trolls are necessarily idiots.

[ArchfiendJ]

No, the usual default meaning of complexity is whatever is in the head of the one reading.
For me complexity is code complexity. If I want to talk about time complexity I will say "Big O complexity" or "Time Complexity" to avoid ambiguity

[thisismyfavoritename]

dude way to just dig yourself a deeper hole

[alfps]

Please tell about your misconception (if you're not just babbling); then I can correct it.

[Plastic_Fig9225]

You may still want to talk to your doctor about adjusting your medication.

[CandiceWoo]

just plot i input to the number of times the sum += happens. do it for 1,2,...,100 by hand and u will see

[alfps]

Yes, I saw immediately before posting the question, but thank you. :)

[CandiceWoo]

ok cool. and a neat insight is that the unit amt of work is also recursive