0
$\begingroup$

It's been a long time since I've studied time complexity in school, but I've been tasked with finding the time complexity of an algorithm. Here is the algorithm in a pseudo-pseudocode (yes, two pseudos because I'm not good at creating pseudocode. Haha!).

main()
{
  list = methodImportFromCSV(...)   // Don't care about this line's complexity

  tree = createRootNode()    // O(1)

  DO
    count = tree.createChildren(list)
  WHILE count > 0
}

createChildren(list) : returns integer
{
  nodesCreated = 0

  foreach (node in this.children)
  {
    nodesCreated += node.createChildren(list)
  }

  groups = separateIntoGroups(list) // O(n)

  foreach (group in groups)
  {
    if (someMethodThatReturnsTrueOrFalse(group) = true) // Some method is O(n) of the group
    {
      this.children.Add(new child())
      nodesCreated += 1
    }
  }

  return nodesCreated
}

You can see that the method is recursive and just creates a tree structure. I remember a few things just as linear iteration is [O(n)], but I've never had to deal with recursion before. Is it permissible to state that the algorithm is running at O(n * t)? Perhaps I am wrong? I thank you, all, for your assistance.

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Feb 3 '18 at 9:38
  • $\begingroup$ Our reference question may help. $\endgroup$ – Raphael Feb 3 '18 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.