I have this algorithm taken out from the Manual of Algorithms Analysis:
function pesky (n) r:=0 for i:=1 to n do for j:=1 to i do for k:= j to i + j do r := r + 1 return (r)
I understand the time complexity of this algorithm for any given input size n > 0 will be O(n^3) since the 3 for loops will always be executed and the inner loop carries out the sum operation n x n x n times (this is of course not exact, but I say it in asymptotic terms taking out constants and lower degree terms of n); however, during a lecture we were asked to express the complexity of the worst-case in terms of n instead of in big oh notation (they left this exercise for next session).
The worst case I can think about for this algorithm would a really large integer as input n which in fact could be so large that it approaches infinity (since no restrictions for the input were stated). Even in this worst case we know time complexity would behave in O(n^3), but how would I express this "in terms of n", the best thing I could come up with is this:
But I feel like I'm just making that up and that there might be another more correct way to express it. Does anyone know the correct way to express worst-case complexity in terms of n?
EDIT: I must make it clear that I found the equation that puts n in function to the r output by means of summation resolving, however I did not consider that function as the time complexity function (and hence not the answer for "worst-case in terms of n") since that function describes output on a given input and not the time it takes to run the algorithm itself.
Moreover I had the idea to try to calculate the complexity counting each operation and I got something like this.
I am not sure if thats correct, if it is I could use that expression to state the worst-case complexity in terms of n, and also I could make my initial statement about big oh notation for the worst case more precise since this would be O(n).