Jratos's blog

Time complexity analysis, mine: O(n^3)
By Jratos, history, 2 weeks ago, In English

Hi, is there a reason why my submission* got accepted meanwhile my rough estimate for time complexity is O(n^3), because i did a dfs and for every node i calculate a subset sum of each subtree size. Or is this because of weak tc? thanks

*) https://codeforces.net/contest/1856/submission/290385616

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

The time complexity will be O($$$n^2$$$). For each node we iterate through it's children and the number of parent-children pairs is n-1. We then calculate the subset sum in O($$$n$$$) leading to O($$$n^2$$$).

→ Reply