Member Avatar for rose_2

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
  • 375 Views
  • 1 Hour Discussion Span
  • Latest Post Latest Post by AssertNull

Dani AI

Generated

Short answer: complexity is a property of operations (methods), not of a class as a whole. Analyze the method you actually call on the object. If the Child only adds a simple setter, that setter is O(1) and the inherited Parent methods keep whatever complexity they already had. If Child overrides a Parent method, inline the Parent cost (or account for its call with super) and then simplify the resulting expression.

A compact workflow to follow:

  1. Pick the public method/operation you need to analyze (constructor, API method, etc.).
  2. For that method, list every work item and every call it makes to other methods (including super calls). Replace each call with its cost function.
  3. If a call happens once per method, add the costs; if it happens inside a loop or is invoked per element, multiply accordingly.
  4. Simplify the sum/product to Big-O by dropping lower-order terms and constants. Also make sure you define the input size variable(s) you are measuring (n, m, etc.).

Example (illustrates override that calls super):

class Parent {
    void compute(int n) {
        // nested loops -> O(n^2)
    }
}

class Child extends Parent {
    @Override
    void compute(int n) {
        super.compute(n);   // O(n^2)
        // extra loop -> O(n)
    } // total work: O(n^2 + n) -> O(n^2)
}

Practical notes: if Child calls a Parent method inside a loop you can get multiplication (e.g., O(n) * O(n) -> O(n^2)). Constructors run the Parent constructor first, so include that cost when measuring object-creation time. Finally, watch for different input measures (Parent uses m, Child uses n) — express the final complexity in terms of the relevant variables. This aligns with the clarification from and addresses 's original question about how inheritance affects overall cost.

Recommended Answers

All 2 Replies

Member Avatar for 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.

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

Edited by AssertNull
Member Avatar for 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
    }
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.