For the following questions, simplify and express your answer as (nk) or (nk (log n)) wherever possibl (showing an explicit value of k). If the running time is exponential, then just give exponential lower bounds Random(n) generates a random number between 1 and n with uniform distribution (every integer between 1 and n is equally likely.) 1. Consider the following function: func1(A, n) /* A is an array of integers 1 if (n ≤ 10) then return (A[1]); 2 for 1 to n do 3 4 5 6 j← 2; while (j≤n - 3) do A[j] ← A[j] + A[j + 1]; j+ 2 × j; end k← Random(n); if (k /
For the following questions, simplify and express your answer as (nk) or (nk (log n)) wherever possibl (showing an explicit value of k). If the running time is exponential, then just give exponential lower bounds Random(n) generates a random number between 1 and n with uniform distribution (every integer between 1 and n is equally likely.) 1. Consider the following function: func1(A, n) /* A is an array of integers 1 if (n ≤ 10) then return (A[1]); 2 for 1 to n do 3 4 5 6 j← 2; while (j≤n - 3) do A[j] ← A[j] + A[j + 1]; j+ 2 × j; end k← Random(n); if (k /
Related questions
Question
Please show steps clearly
![For the following questions, simplify and express your answer as (nk) or (nk (log n)) wherever possible
(showing an explicit value of k). If the running time is exponential, then just give exponential lower bounds.
Random(n) generates a random number between 1 and n with uniform distribution (every integer between
1 and n is equally likely.)
1. Consider the following function:
func1(A, n)
/* A is an array of integers
1 if (n ≤ 10) then return (A[1¹]);
1 to n do
2 for
3
4
5
6
j ←2;
while (j ≤ n - 3) do
A[j] ← A[j] + A[j + 1];
j← 2 × j;
end
k← Random(n);
if (k <n/5) then return (A[1]);
7
8
9
10 end
11 return (A[n]);
(a) What is the asymptotic worst-case running time of func1? Justify your solution.
(b) What is the asymptotic expected running time of func1? Justify your solution.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F2eec24dd-db09-4176-a5fa-f06d09558dc3%2F08eb716f-5643-4169-a399-1240caf0c125%2Fk0c67eb_processed.png&w=3840&q=75)
Transcribed Image Text:For the following questions, simplify and express your answer as (nk) or (nk (log n)) wherever possible
(showing an explicit value of k). If the running time is exponential, then just give exponential lower bounds.
Random(n) generates a random number between 1 and n with uniform distribution (every integer between
1 and n is equally likely.)
1. Consider the following function:
func1(A, n)
/* A is an array of integers
1 if (n ≤ 10) then return (A[1¹]);
1 to n do
2 for
3
4
5
6
j ←2;
while (j ≤ n - 3) do
A[j] ← A[j] + A[j + 1];
j← 2 × j;
end
k← Random(n);
if (k <n/5) then return (A[1]);
7
8
9
10 end
11 return (A[n]);
(a) What is the asymptotic worst-case running time of func1? Justify your solution.
(b) What is the asymptotic expected running time of func1? Justify your solution.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 4 steps with 34 images
