Complexity of Naive Recursion
In this popular forum thread the author claims that the complexity of the naive recursion is exponential:\n\n"The time complexity for the naive recursion in ste
In [this](https://leetcode.com/problems/house-robber-iii/discuss/79330/Step-by-step-tackling-of-the-problem) popular forum thread the author claims that the complexity of the naive recursion is exponential:\n\n"The time complexity for the naive recursion in step I is indeed exponential. For each tree node tn at depth d, let T(d) be the number of times the rob function will be called on it. Then we have T(d) = T(d - 1) + T(d - 2). This is because rob will be called on tn either from its parent (at depth d - 1) or its grandparent (at depth d - 2), according to its definition. Note T(0) = T(1) = 1, i.e., rob will be called only once for the tree root and its two child nodes. Therefore T(d) will essentially be the (d+1)-th Fibonacci number (starting from 1), which grows exponentially (more info can be found here)."\n\nThere is discussion in the comments about it actually being O(N^2) because the d (tree depth) in the T(d) above, scales logarithmically with the number of nodes. The author is right that in the worst case it scales exponentially. But for a balanced tree the scaling is indeed polynomial but not O(N^2) as I thought. I figured there was a 4 way branching so 4^log(N)->N^2. Empirically I find ~O(N^1.68157) for a perfectly balanced tree.\n\nI imagine the ~1.68157 corresponds to 1+log2(\u03C6) (\u03C6=(1+sqrt(5))/2) because the scaling of T(d) is \u03C6^d=\u03C6^log2(N)=2^(log2(N)log2(\u03C6))=N^log2(\u03C6). As the definition of T(d) was the number of calls per node at depth d we still have to multiply by N (half the nodes are at the leaves) to obtain N^(1+log2(\u03C6))=N^(1.694...) which my empirical result would hopefully converge to if I let it run longer.\n\n![image](https://assets.leetcode.com/users/agade/image_1567281975.png)\n\nLocal code\n```\n#include <iostream>\n#include <fstream>\n#include <chrono>\n#include <random>\nusing namespace std;\nusing namespace std::chrono;\n\ndefault_random_engine generator(system_clock::now().time_since_epoch().count());\nuniform_int_distribution<int> Val_Generator(0,25);\n\nstruct TreeNode{\n\tint val;\n\tTreeNode *left,*right;\n\tTreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n};\n\nint rob(const TreeNode *root,const bool can_take){\n\tif(root==nullptr){\n\t\treturn 0;\n\t}\n\tif(can_take){\n\t\treturn max(root->val+rob(root->left,false)+rob(root->right,false),rob(root->left,true)+rob(root->right,true));\n\t}\n\telse{\n\t\treturn rob(root->left,true)+rob(root->right,true);\n\t}\n}\nint rob(const TreeNode* root){\n    if(root==nullptr){\n\t\treturn 0;\n\t}\n\treturn rob(root,true);\n}\n\nvoid Add_Leaves(TreeNode *root){\n\tif(root->left!=nullptr){ //root->right is automatically not null because we only use balanced trees\n\t\tAdd_Leaves(root->left);\n\t\tAdd_Leaves(root->right);\n\t}\n\telse{\n\t\troot->left=new TreeNode(Val_Generator(generator));\n\t\troot->right=new TreeNode(Val_Generator(generator));\n\t}\n}\n\nint main(){\n\tTreeNode *root=new TreeNode(Val_Generator(generator));\n\tofstream Timing_File("Time_Logs.txt",ios::trunc);\n\tfor(int depth{1};depth<25;++depth){\n\t\ttime_point<high_resolution_clock> start{high_resolution_clock::now()};\n\t\trob(root);\n\t\tTiming_File << pow(2.0,depth-1) << " " << depth << " " << (high_resolution_clock::now()-start).count() << endl;\n\t\tAdd_Leaves(root);\n\t}\n}\n```\nMakefile\n```\nall:\n\tg++ Local.cpp -o Local -std=c++17 -O3 -march=native -g\n```\nGnuplot script\n```\nset terminal pngcairo\nset output \'Timing_vs_N.png\'\nset title \'Runtime vs N\'\n\na=1\nc=2\nf(x)= a*x**c\nfit f(x) "Time_Logs.txt" using 1:3 via a,c\n\nplot "Time_Logs.txt" using 1:3,\\\n\tf(x)\n```
[]