CODEWITHSUNDEEP
algorithm
EsotericLanguage
EsotericLanguage

Reputation: 149

Big O Notation With Separated Procedures

Today marks the first day I begin to study Algorithms and Algorithm Analysis. More specifically asymptotic analysis. But before I dive in I have one simple question that needs clarification that I cant seem to find anywhere else. Given the code snippet below what would the algorithm complexity be in Big O notation?

// Linear Computation: O(n)
    ....

//Merge Sort: O(n log(n))
    ....

//Merge Sort: O(n log(n))
    ....

//Nested for loops iterating n times each: O(n^2)
    ....

My assumption would be Big O: O(n) + (2 * O(n log (n) )) + O(n^2) but by definition of Big O do we simplify this further? Would we just call this program O(n^2) considering it is the worse of the three and can be upper bounded by a constant c * n^2?

Upvotes: 0

Views: 66

Answers (4)

Vishal_898
Vishal_898

Reputation: 300

When calculating time complexities, we compute it in terms of BIG-O. Now as our programs are huge it is not possible to compute the total of all complexities and on the other hand, there is no sense of doing it because in any expression consisting of big and small terms, if we change big terms then there will significant change in value but if we change small-term then there is no significant change. For eg take value 10000021 if we change leading one to 2, now our value will be 20000021 (huge change), now change ending 1 to 2, now our value will be 10000022 (little change). Similarly, when the program contains n^2 it is considered instead of o(n) or O(logn) . Change in n^2 is not considered. Therefore we consider n^2.

Order -- n! , 2^n , n^R ..... , n^3 , n^2 , nlogn , n , logn

Consider the maximum which is present in the program.

Upvotes: 2

another_CS_guy
another_CS_guy

Reputation: 682

Usually, when calculating time complexities, large value of input is kept in mind. Say like n value is 1000000.

When you say,

Big O: O(n) + (2 * O(n log (n) )) + O(n^2), for this large n, 'n' and (2 * O(n log (n) )) will not grow as much as O(n^2).

So the O(n^2) is the complexity decider for large n, and thatswhy overall complexity given is O(n^2)

Upvotes: 1

Carlos
Carlos

Reputation: 6021

The n^2 term dominates, so the big-O is going to be that. The fact that there's two nlogn terms doesn't change anything, since there's a fixed number of them. And when n is big, n^2 is bigger than nlogn.

Upvotes: 1

user1196549
user1196549

Reputation:

For given C1, C2, C3, you can find C such that

C1 n + C2 n log(n) + C3 n² <= C n²

Upvotes: 1

Related Questions