CODEWITHSUNDEEP
javaalgorithmbig-o
Filipe Nóbrega
Filipe Nóbrega

Reputation: 667

Big-O notation and recursion with loops

What is the Big-O notation of the worst case in the following method: 

 /**
 * @best-case  O(1)
 * @worst-case O(?)
 *
 * {@link NTree#contains(Comparable)}
 */
public boolean contains(T elem) {

    if (this.data.compareTo(elem) == 0)
        return true;

    for(NTree<T> t : children) {
        if(t != null)
            return t.contains(elem);    
    }


    return false; 
}

This is an n-ary generic tree, and each tree has a n number of children. The best case happens when the elemequals the root.data.

But I'm not sure about the worst case where we have to go through every child of the tree.

Upvotes: 2

Views: 682

Answers (3)

Carcigenicate
Carcigenicate

Reputation: 45826

To quote you at the end there:

... the worst case where we have to go through every child of the tree.

If you're going through every child in the worst case, that would be O(n), where n is the number of nodes in the tree.

You can think of it way: if this was a simple linked list, and you had to search through it entirely in the worst case, what would the worst case complexity be? It's the same here. It's just that in this case, each node can have more than one child.

And recursion doesn't really play a role here in altering the complexity. It's just the means to loop. It would be the same if you were doing an iterative search using a standard loop construct.

Upvotes: 5

Temple
Temple

Reputation: 1631

In worst case you will always have to traverse all elements. You can imagine that in real world application when N-ary tree will be used as data structure for filesystem. Each node is file (directory or regular file) and you want to find file by name that is on the right bottom corner of the tree, you can't do it without checking all nodes it is odd to store some additional information to direct you to file faster(this is for example what find command under linux will do when searching file by name).

Upvotes: 0

ShaharA
ShaharA

Reputation: 903

If the n-ary tree has no structure (keys of childs / nodes have no comparison-based sorting) then worst case will be O(N).

If the n-ary tree is not necessarily balanced (meaning each node can have one child in the worst case) then worst case will be also O(N).

If tree is a balanced and sorted n-ary tree O(log2(n) logn(N)) Where:

  • N = #nodes in tree
  • n = #number of children in each node

Explanation:

Binary search in n children will take O(log2(n)), over the depth of the tree, which is maximum O(logn(N)) in a balanced n-ary tree.

Upvotes: 1

Related Questions