Determine the running time of the following algorithm. Write summations to represent…
- User
Determine the running time of the following algorithm. Write summations to represent loops and solve using bounding. Be sure to show work on both the upper bound and lower bound, justify the split, and check that the bounds differ by only a constant factor. Use asymptotic notation to write the answer.
Func1(n) 1 s ← 0; 2 for i ← n to n^2 do 3 for j ← 1 to i do 4 for k ← 9n to 10n^2 do 5 for m ← i to k 6 s ← s + i - j + k-m; 7 end 8 end 9 end 10 end 11 return (s);
Make sure to split the top and make it as the new lower bound
- Assistant
To determine the running time of the given algorithm, we need to analyze the nested loops. Given the dependence of each nested loop on its parent, we can write the total number of iterations as a series of summations.
We are interested in bounding the running time T(n) from above and below, so let's first calculate the summation of the innermost loop (the
mloop) and then work our way outward to the other loops.The innermost loop runs from
m = itom = k. The number of iterations of this loop is given byk - i + 1.Let's move outward to the
kloop. Thekloop runs fromk = 9ntok = 10n^2. The number of iterations varies for each value ofi, but we can establish an upper bound by acknowledging that the innermost loop always executes at most10n^2 - i + 1times for each value ofk.Now sum over all values of
kto get the total running time contributed by thekloop. However, since the inner loop's iterations depend onk, we are interested in a single term of the inner loop (constant term with respect tok) to bound this:[ \sum_{k=9n}^{10n^2}(10n^2 - i + 1) ]
This can be simplified to:
[ (10n^2 - i + 1)(10n^2 - 9n + 1) \approx O(n^4) ]
Continuing with the
jloop, which runs fromj = 1toj = i. We need to sum the above calculation over all values ofj. Since thejloop doesn't significantly increase the number of iterations, we can consider a single iteration fromjto obtain an upper bound (since the calculation above forkgives the max value for anyj):[ \sum_{i=n}^{n^2} O(n^4) = O(n^4) \cdot n^2 = O(n^6) ]
Now we are at the outermost loop (
iloop). The above calculation established the complexity for a single iteration of theiloop, and we must now sum this over allifromnton^2.For the upper bound (UB), we consider the maximum iteration count over the entire range of
i:[ UB = \sum_{i=n}^{n^2} O(n^6) \approx O(n^6) \cdot n^2 = O(n^8) ]
For the lower bound (LB), we split the top as requested, and make
n^2 / 2the new lower bound fori. We consider the minimum iteration count for the portion fromn^2/2ton^2.[ LB = \sum_{i=n^2/2}^{n^2} O(n^4) \approx O(n^4) \cdot (n^2 - n^2/2) = O(n^4) \cdot n^2/2 ]
Even though we notice that the LB scales with
n^6, it is still an overestimate of the actual lower bound required for bounding from below to demonstrate the difference is constant.For the actual LB, let's look at the smallest possible number of iterations of the innermost loop. The minimum occurs when
kandiare the smallest, andm = k, yielding only one iteration. So fork = 9n,i = n, andm = 9n, we have:[ LB = \sum_{i=n}^{n^2} 1 (9n^2 - n + 1) = 9n^4 - n^3 + n^2 \approx O(n^4) ]
This is the correct lower bound to demonstrate the split between UB and LB. The bounds differ by a factor of
n^4, but can be considered constant relative to the magnitude of their growth. Therefore, multiplying the lower bound byn^4gives us the tightest upper bound.In summary, the running time of the given algorithm Func1(n) is bounded by O(n^8) from above and Ω(n^4) from below, showing that the algorithm’s running time is O(n^8) as the asymptotically tight upper bound allows us to ignore the lower bound difference due to the constant factor.