CODEWITHSUNDEEP
algorithmbig-o
spiroth10
spiroth10

Reputation: 31

how to calculate the total big O value of two algorithms -- is it just O(|f1| + f|2|)?

say I know the order of magnitude of both algorithms already -- for simplicities sake I will assume O(nLogn) and O(n^2).

is the answer just O(|nLogn| + |n^2|) or can I somehow get it into simpler terms?

I believe if I know the value of n, I could just plug it into the equation, since the total amount of work is the max running time of both.

i know its probably a a stupid question lol.

Upvotes: 1

Views: 50

Answers (1)

Stephen C
Stephen C

Reputation: 719299

I know its probably a a stupid question.

Not stupid, but it does indicate that you have not fully grasped what Big O notation means mathematically ... or intuitively. You should go back to your lecture notes / textbook and reread what they say.

Intuitively, when we say that f(x) is O(g(x)) that means that f(x) tends towards being proportional to g(x) as x gets very big.

So for your example,

  • a(n) is O(nlogn) and b(n) is O(n^2)
  • a(n) + b(n) is O(nlogn + n^2)

but

  • O(nlogn + n^2) is the same as O(n^2), because as n gets very large, nlogn + n^2 tends to being proportional to n^2. (The nlogn term gets relatively smaller until eventually it is no longer significant.)

so

  • a(n) + b(n) is O(nlogn + n^2) which is the same as O(n^2)

This can also be proven mathematically, if you are so inclined (or required).

Upvotes: 4

Related Questions