What is the worst case running time, in big-Oh notation, of the following program?
Code:int function(int n) { r=0; for (i=1; i<n; i++) for (j=i+1; j<n+1; j++) for (k=1; k<=j; k++) r++; return r; return 0; }
This is a discussion on Complexity using big-Oh notation within the C Programming forums, part of the General Programming Boards category; What is the worst case running time, in big-Oh notation, of the following program? Code: int function(int n) { r=0; ...
What is the worst case running time, in big-Oh notation, of the following program?
Code:int function(int n) { r=0; for (i=1; i<n; i++) for (j=i+1; j<n+1; j++) for (k=1; k<=j; k++) r++; return r; return 0; }
I feel confident that this is O(n! n^n e^n). You can probably come up with a sharper estimate, though, if you try.
(I.E. and in other words: show some effort and we will look more kindly upon the question.)
If the result was O(n^2), and using the fact that the outer loop goes from 1 to n, that would suggest that the inner two loops together execute in O(n). Does that seem possible?
I took it step by step
for i=1
first loop o(1), second o(n-1), third o(2)*o(2)*...*o(n) ---> that is o(n*n!)
for i=2
first loop o(1), second o(n-2), third o(3)*...*o(n)
and so on
for i=n-1
first loop o(1) second o(1), third o(n)
And then we add them.
Is this how it works?
The first loop isn't O(1), it's O(j) -- more specifically, it's exactly j. So that means your second loop, you need to add up j as j goes from i+1 to n+1 (you should hopefully have a formula for that). Then that value gets added as i goes from 1 to n.