CODEWITHSUNDEEP
c++big-o
user2726232
user2726232

Reputation: 131

In Big O notation, how do you factor in calls to other methods?

Hypothetically, lets say we have these two methods:

void example(int p){
    p += 10;
    p = exampleTwo(p);
}

int exampleTwo(int p){
    int pp = 0;
    for(int i = 0; i < p; i++){
        pp++;
    }
    return pp;
}

The method exampleTwo has a linear runtime. Its run time is O(n).

So, what is the big O notation of the method example, taking into account that it calls exampleTwo?

I would imagine it is also O(n), but I do not know for sure.

Upvotes: 4

Views: 2581

Answers (2)

Darren Cook
Darren Cook

Reputation: 28968

example() has no loop, it does nothing extra to exampleTwo() so it has the same order of complexity, i.e. O(n), as exampleTwo().

If example() is changed to this:

int example(int p){
  int sum = 0;
  for(int i=0; i<p; ++i){
    sum += exampleTwo(p);
    }
  return sum;
}

then the complexity is now O(n²): as p gets bigger the amount of work to do increases by the square of p.

Upvotes: 5

Dan
Dan

Reputation: 12705

For subroutines, you should multiply the order by the order of the number of the number of times it is called. For example, if a function is called O(n) times, and runs in O(log n) time, the total order is O(n log n).

Upvotes: 6

Related Questions