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
1 Year
Discussion Span
Last Post by AssertNull

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.

Edited by AssertNull

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.