CODEWITHSUNDEEP
big-otime-complexity
Bar
Bar

Reputation: 194

Regarding time complexity, big O notation

suppose n1,n2 > k. Does 

 O(k(n1+n2-k)) = O(k(max(n1,n2)) ?

Also, does

 O(n1+n2) = O(max(n1,n2)) ?

Thanks

Upvotes: 2

Views: 157

Answers (1)

amit
amit

Reputation: 178411

Is the claim O(k(n1+n2-k)) = O(k(max(n1,n2)) true?

We know that k < min{n1,n2} - thus:

k(n1+n2-k) = k(max{n1,n2} + min{n1,n2} -k) > k(max{n1,n2})

So, it is pretty trivially to show that O(k(max(n1,n2)) is a subset of O(k(n1+n2-k))

We also need to show the other way around, which is also pretty easy because 2k*max{n1,n2} is in O(k(max(n1,n2)), and 

k(n1+n2-k) < k(max{n1,n2} + max{n1,n2}) -k) < 
           < k(max{n1,n2} + max{n1,n2}))
           = 2 k*max{n1,n2}

So, the claim is correct.

Does O(n1+n2) = O(max(n1,n2)) ?

This is correct. Since max{n1,n2} <= n1+n2 <= 2*max{n1,n2}, and we don't care about constants when analyzing big O notation.

Upvotes: 3

Related Questions