CODEWITHSUNDEEP
data-structurestime-complexity
user6575289
user6575289

Reputation:

What is the complexity in the following case?

Suppose we have a while loop that iterates on the basis of a true-false condition (let suppose whether a queue is empty or not) and it has a for loop inside like:

while(!queue.isEmpty()) {
    // some lines of code
    for(int i = 0; i < n; i++) {
        // some code
    }
}

Will it be O(n^2) or O(n).

EDIT

 while(!queue.isEmpty()) {
        currNode = queue.remove();
        indexToSearch = currNode.data;
        for(i = 0; i < parentArr.length; i++) {
            if(parentArr[i] == indexToSearch) {
                newNode = new BinaryNode(i);
                if(!leftDone) {
                    currNode.left = newNode;
                    queue.add(newNode);
                    leftDone = true;
                } else {
                    currNode.right = newNode;
                    queue.add(newNode);
                    break;
                }
            }
        }
        leftDone = false;
    }

Upvotes: 0

Views: 187

Answers (1)

user2887596
user2887596

Reputation: 643

In this case, your complexity depends on both n and the size of your queue. So that your complexity would be O(n * queue.size())

(assuming that your other implied lines of code can be ignored)

In order to determine a "useful" complexity class, you need to include all of the parameters that can change the number of iteration you have to go through.

(Also, since you never pop your queue, in the worst case you will have a function that diverges, but I guess it is implied that you pop your queue before or after the loop)

***********EDIT**** (after seing the code)

So you have an array of n values. And wish to construct a tree with n nodes

For each node you add: (meaning n times)
    You linearly search your array of values (worst case: you always need to search the entire array, also meaning n times)

So your complexity is O(n^2 )

(If you wouldn't be able to make the assumptions above you would get an other complexity because of stuff like 'what if the value is not in the queue' or 'what if my queue is much larger than the array' )

Upvotes: 1

Related Questions