▲ 0 r/cpp_questions
Complexity of a simple function.
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 ) ); }
u/alfps — 5 hours ago