Determine the running time of the following algorithms. Func1(n) 1 s ← 0; 2 for i ← 3n…
- User
Determine the running time of the following algorithms.
Func1(n) 1 s ← 0; 2 for i ← 3n to 〖3n〗^2 do 3 for j ←2i to 2i^2 do 4 s ← s + i - j; 5 end 6 end 7 return (s);
- Assistant
To determine the running time of
Func1(n), we'll analyze the nested loops in the algorithm.The outer loop:
for i ← 3n to 〖3n〗^2 doThis loop starts with
i = 3nand runs untili = (3n)^2. The increment is 1 for each iteration, so it will run for a total of((3n)^2 - 3n + 1)iterations.The inner loop:
for j ← 2i to 2i^2 doFor each value of
i, the inner loop starts withj = 2iand runs untilj = 2i^2. Similar to the outer loop, the increment here is also 1 for each iteration. Therefore, for each value ofi, the inner loop will run for2i^2 - 2i + 1iterations.To find the total running time of the algorithm, we need to sum up the number of iterations for each possible
i. Let's express the overall running time as a sum:Total number of iterations = Σ (from i = 3n to (3n)^2) [2i^2 - 2i + 1]This formula gives us the sum of the running times for each individual iteration of
i, which will be a 5th-degree polynomial since the inner sum contains i squared. Calculating this polynomial exactly can be complex, but we're typically more interested in the asymptotic behavior (Big O notation) rather than the exact number of iterations.The dominant term in the polynomial will be when
iis at its maximum value, which happens to be(3n)^2. Wheniis at its maximum, the2i^2term dominates the inner sum. Thus, each iteration of the inner loop will contribute a term proportional to(3n)^4when we're at the tail end of the outer loop range.When considering Big O notation, we only focus on the largest term since it dominates the running time when
ngrows large. We can thus approximate our sum as:Total running time ∝ ((3n)^2 - 3n + 1) * (3n)^4 Total running time ∝ (9n^2) * (81n^4) Total running time ∝ 729n^6So we can say that the running time of
Func1(n)is O(n^6). It's polynomial time with a degree depending on the squared terms in the loops, but we express it in Big O notation as the highest power ofnthat appears in the formula.