3) How much time does the following “algorithm” require as a function of n? l=0 for...

Question

Question

3) How much time does the following “algorithm” require as a function of n?

l=0

for i=1 to n do

for j=1 to i do

for k=j to n do

l = l + 1

Answer 1

Answer #1

First for loop runs for n times.
Second for loop runs for i times.
Third for loop runs for n-j times.

Summation = Π. Π 2 ΣΣΣ: 2-1 i= 1 j = 1 k=i

So, Time complexity = O( n^3 )

Answer 2

Similar Homework Help Questions

How much time does the following "algorithm" require as a function Problem 4.1. of n? for...

How much time does the following "algorithm" require as a function Problem 4.1. of n? for i 1 to n do for j 1 to n do for k 1 to n3 do Express your answer in 6 notation in the simplest possible form. You may consider that each individual instruction (including loop control) is elementary
Consider the following algorithm. ALGORITHM Enigma(A[0.n - 1]) //Input: An array A[0.n - 1] of integer...

Consider the following algorithm. ALGORITHM Enigma(A[0.n - 1]) //Input: An array A[0.n - 1] of integer numbers for i leftarrow 0 to n - 2 do for j leftarrow i +1 to n - 1 do if A[i] = = A[j] return false return true a) What does this algorithm do? b) Compute the running time of this algorithm.
Perform the following to the algorithm below: - - Express T(n) as a function of n...

Perform the following to the algorithm below: - - Express T(n) as a function of n Find a best approximation for the Big O function for T(n) Perform a time complexity analysis Define the basic operation of the algorithm Correctness Efficiency - - Procedure maxMin (n, A, I, h) integer h, I, A (1:n), n integer j j-2 IA (1) hS (1) while (i <=n) do if (Ali) < 1) then TEA (0) if(Ali) >h) then h A() j+į+1 repeat...

Give a linear (O(n)) time algorithm sorting n values in range 0..(n^3) − 1. (Hint: represent...

Give a linear (O(n)) time algorithm sorting n values in range 0..(n^3) − 1. (Hint: represent a value x as (i, j, k) where x = i · (n^2) + j · n + k.)
Analyze the running time of the following algorithms asymptotically. (a) Algorithm for-loop(n): P = 1 for...

Analyze the running time of the following algorithms asymptotically. (a) Algorithm for-loop(n): P = 1 for i = 1 to 5n^2 do p = p times i return p (b) Algorithm for-loop(n): s = 0 for i = 1 to n do for j = I to n do s = s + i return s (c) Algorithm WhileLoop(n): x = 0; j = 2; while (j = n){x = x+ 1; j =j times 2;}
(V). Given the following algorithm, answer relevant questions. Algorithm 1 An algorithm 1: procedure WHATISTHIS(21,22,...,n: a...

(V). Given the following algorithm, answer relevant questions. Algorithm 1 An algorithm 1: procedure WHATISTHIS(21,22,...,n: a list of n integers) for i = 2 to n do c= j=i-1 while (j > 0) do if ra; then break end if 4j+1 = a; j= j-1 end while j+1 = 1 end for 14: return 0.02. 1, 15: end procedure Answer the following questions: (1) Run the algorithm with input (41, 02, 03, 04) = (3, 0, 1,6). Record the values...

ALGORITHM X(A[0..n - 1]) // Input: A contains n real numbers for it 0 to n...

ALGORITHM X(A[0..n - 1]) // Input: A contains n real numbers for it 0 to n - 2 do for jt i +1 to n - 1 do if Aj] > A[i] swap A[i] and A[j] 1. What does this algorithm compute? 2. What is the basic operation? 3. How many times is the basic operation executed? 4. What is the efficiency class of this algorithm?
3. Recursive Program (6 points) Consider the following recursive function for n 1: Algorithm 1 int...

3. Recursive Program (6 points) Consider the following recursive function for n 1: Algorithm 1 int recurseFunc(int n) If n 0, return 1. If n 1, return 1 while i< n do while j <n do print("hi") j 1 end while i i 1 end while int a recurse Func(n/9); int b recurse Func (n/9) int c recurse Func (n/9) return a b c (1) Set up a runtime recurrence for the runtime T n) of this algorithm. (2) Solve...
Analyze the time complexity of the following algorithm. You may assume that the floor function in...

Analyze the time complexity of the following algorithm. You may assume that the floor function in line 2 takes Theta (1) time. Please show your work. Input: data: array of integers Input: n: size of data Output: median of data 1 Algorithm: MedianSelect 2 lim = [n/2] + 1 3 min = - infinity 4 for i = 1 to lim do 5 prev = min 6 min = infinity 7 for j = 1 to n do 8 if...

Question 2 Consider the following algorithm Fun that takes array A and key Kas Fun(AO,...,n -...

Question 2 Consider the following algorithm Fun that takes array A and key Kas Fun(AO,...,n - 1], K) count = 0 for i = 0 ton - 1 do for j = i +1 to n - 1 do if A[i] + A[j] == K then count = count +1 end if end for end for return count What is the best case time complexity of the above algorithm?! (log(n)) O(1) (n) (na) Previous o H H 9