Big O notation for these algorithm complexities

user_15226855 0
Viewed 30

I have a few algorithm complexities that I'm not entirely sure of what the Big O notations are for them.

i) ((n-1)(n-1) * ... * 2 * 1)/2

ii) 56 + 2n + n^2 + 3n^3

iii) 2n(lg n) + 1001

iv) n^2 * n^3 + 2^n

I believe ii) and iii) are pretty straightforward with the Big O of ii) being O(n^3) and the Big O of iii) being O(n log n) but let me know if these are wrong.

It's mostly i) and iv) I'm a bit confused on. For i) I assumed it followed the same idea as 1+2+3+4+...+n which has a Big O notation of O(n^2) so that's what I put and for iv) I put O(n^5) but I'm not sure if the 2^n affects the Big O notation in this case, I'm not sure what gets priority here or do I just include them both?

Any help would be much appreciated, I'm not that experienced in Big O notation so any advice would be really helpful as well.

Thanks in advance

big-o time-complexity
1 Answers

Since problem i) is multiplying (not adding) the terms from 1 to n, that should be O(n!).

You're right on ii) n^3 is the dominant term, so it's O(n^3), and on iii) both constants 2 and 1001 can be ignored leaving you with O(n log n).

On iv) you were right to combine the first two terms to get n^5, but even that will eventually be surpassed by the 2^n term, so the answer is O(2^n).

Bill_the_Lizard_12880
Related