0

If I have the following code, let's say the Parent class has the complexity of O(n^2) according to methods included in the Parent. So if I want to calculate the complexity of inherited class (Child class), does it take the Parent class complexity and its own complexity? something like that complexity of child class = O(O(Parent)+O(Child)) ?

public class Parent {
    private int number;

   // more stuff
}
public class Child extends Parent {
    public void setNumber(int newNum){
        this.number = newNum;
    }
}
2
Contributors
2
Replies
21
Views
10 Months
Discussion Span
Last Post by AssertNull
1

You don't add Big-O values. You can multiply them or do any number of other operations on two or more Big-O values, but you don't add or subtract them. This is independent of what the two Big-O values might represent and whether they are classes or subclasses or how the operations are related or the data involved, etc. You never add or subtract Big-O values.

If you have operation A and operation B and operation A starts and finishes, then operation B starts and finishes, then total time is time(A) + time(B), but the Big-O will be the MAXIMUM of the Big-O of operation A and the Big-O of B, so if O(A) is n and O(B) is nlogn, then O(A and B) is nlogn.

If A CALLS B once every iteration, you could multiply. Consider printing an nxn grid where function B prints a row and print A prints the whole grid. Or anything else like this...

void A(int n)
{
    // O(nlogn)
}

void B(int n)
{
    for(int i = 0; i < n; i++)
    {
        A(n); // n total calls to function B
    }
}

In this case, multiply n times nlogn and get n^2logn.

So, long story short, "it depends", but one thing it will definitely NOT be is the sum of two Big-O values. Most common in the situation you describe, I imagine you would take the maximum of the two Big-O values, but that's a generalization.

http://stackoverflow.com/questions/1734030/how-to-add-merge-several-big-os-into-one

Edited by AssertNull

0

Whoops. Got A and B mixed up above. Should be this. Hopefully concept was clear.

void B(int n)
{
    // O(nlogn)
}

void A(int n)
{
    for(int i = 0; i < n; i++)
    {
        B(n); // n total calls to function B
    }
}
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.