What is the value returned by the following function? Express your answer as a function of n. Give using O() notation the worst-case running time.
Pseudo code of the algorithm:
F1(n)
v = 0
for i = 1 to n
for j = n + 1 to 2n
v++
return v
My approach:
The output of F1(n) is a integer value returned from the variable v which is calculated by the inner for-loop during iteration on size 2n and on size n for the outer for-loop.
The variable v is initialized as 0 before the iterations of both loops begin. When the ith for-loop is at the 1st ith iteration then the jth for-loop(inner for-loop) iterates from size n+1 to 2n. Suppose n = 5 then the jth for-loop iterates from j = 6 to 10, this means the number of times v is incremented for 1 full iteration of the inner for-loop.
Since the jth for-loop always increments v by n-1(4 in this case) then in each full iteration this means when the ith for-loop starts from 1 to n then the variable v is incremented by n-1 times for every i iteration.
So this algorithm maps the function g(n) = (n-1) * (n-1). Which will be 4 * 4, so v = 16 when n = 5. This is true because when n = 5 every full jth iteration v is incremented by 4. So if the ith for-loop runs from i =1,…,4(1 to n) then v is incremented by 4 every time i is incremented so this explains why the result would be (n-1 * n-1) as the answer.
The worst-case Big Oh complexity for this program is O(n^2) because it has a nested loop structure where the outer loop iterates through 1 to n times and the inner loop iterates through n+1 to 2n times which is also equivalent to n times because it is iterating through all values of n.
Lastly, the initialization/incrementing of a variable takes O(1) time so this does not affect the complexity much in comparison to the nested for-loop.
To me this maps g(n)=n^2 function since loop for i=1 to n runs n times if you count all values from range [1,n]. Of course if it is [1,n) then you have g(n)=(n-1)^2 but that's matter of convention.
Two nested loops , each running n times give you O(n^2) complexity which is best-average-worst in this case. So your approach is fine if that was your question :)