Hack Forums
[Java] Space complexity algorithm - Printable Version

+- Hack Forums (https://hackforums.net)
+-- Forum: Tech (https://hackforums.net/forumdisplay.php?fid=444)
+--- Forum: Coding (https://hackforums.net/forumdisplay.php?fid=151)
+---- Forum: Software Development (https://hackforums.net/forumdisplay.php?fid=118)
+---- Thread: [Java] Space complexity algorithm (/showthread.php?tid=5206121)

Space complexity algorithm - humanjas - Mar 17, 2016

Code
1 public int pathlength(Tree t) {
2 return pathlength(t.root(), 0);
3 }

4 private int pathlength(Node v, int depth) {
5 if (v == null) return depth;
6 int result = depth;
7 for (Node c: v.children())
8 result += pathlength(c, depth+1);
9 return result;
10 }
How do you start calculating the space complexity of this through recurrence equations?

I started with the base case, which is a constant 'c1'.

Then they have a recursive call which is 'h' times a constant 'c2'. 'h' is the amount of children of the root.

But how do you continue with this?

Thanks in advance.

* - Stealth™ - Mar 18, 2016

Are you trying to find the height of the longest path? Or the total number of nodes?

* - humanjas - Mar 26, 2016

Already found the answer. I had to calculate the space complexity of this algorithm, using recurrence equations. The answer was O(h), I thought too complicated.