What is the time-complexity of the algorithm abc?
Procedure abc(n: integer) s := 0
i :=1
while i ≤ n
s := s+1
i := 2*i return s
consider the following algorithm:
Procedure foo(n: integer) m := 1
for i := 1 to n
for j :=1 to i2m:=m*1
return m
c.) Find a formula that describes the number of operations the algorithm foo takes for every input n? d.)Express the running time complexity of foo using big-O/big-
Solution:
(1)
Explanation:
Finding time complexity of abc algorithm:
=>We can see in the abc() method, there is a while loop starting from i = 1 and ending with condition i n doubling the value of i each time using i = 2i
=>Number of times loops will be executed = log(n) times
=>Time complexity of abc algorithm = O(logn)
(2)
(c)
Explanation:
=>In procedure foo() we can see that there are 2 for loops.
=>Outer for loop is independent for loop loop and will run n times from i = 1 to i = n incrementing the value of i by 1 each time.
=>Inner for loop is dependent for loop and will run from j = 1 to j i incrementing the value of j by 1 each time.
=>Total number of times loops will be executed = 1 + 2 + 3 +....+ n
=>Total number of times loops will be executed = n(n+1)/2
=>Let say cost of comparisons and other operation takes time = C where C is some constant.
=>Cost of all operations = n(n+1)/2 + C
(d)
Explanation:
=>Cost of all operations = n(n+1)/2 + C
=>Hence time complexity in big-O = O(n^2)
I have explained each and every part with the help of statements attached to it.
What is the time-complexity of the algorithm abc? Procedure abc(n: integer) s := 0 i :=1...
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.
(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...
[10 marks] consider the following pseudocode: p := 0 x := 2fori:= 2ton p := (p + i ) * x a) How many addition(s) and multiplication(s) are performed by the above pseudocode?b) Express the time-complexity of the pseudocode using the big-Θ notation.) Trace the algorithm, below, then answer (c) and (d): Procedure xyz(n: integer) s := 0, for i:= 1 to n, for j:= 1to i, s:= s+ j*(i− j+ 1) return s c) What is the time-complexity for...
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...
Let T(n) be the running time of function foo. Find the equation of T(n) and find the complexity of T(n) using big-O notation. def foo(L): s = 0 for x in L: j = len(L) while j > 1: j = j / 2 s = s + x print(s) return s
Exercise 7.3.5: Worst-case time complexity - mystery algorithm. The algorithm below makes some changes to an input sequence of numbers. MysteryAlgorithm Input: a1, a2....,an n, the length of the sequence. p, a number Output: ?? i != 1 j:=n While (i < j) While (i <j and a < p) i:= i + 1 End-while While (i <j and a 2 p) j:=j-1 End-while If (i < j), swap a, and a End-while Return( aj, a2,...,an) (a) Describe in English...
1- Find the time complexity of the following program, where n is given as input: i = n; while (i > 1) { j = i; while (j < n) { k = 0; while (k < n) { k += 2; } j *= 2; } i /= 2; } Express your answer using theta notation, and explain the amount of time it takes for each loop to finish.
What is the worst-case asymptotic time complexity of the following divide-andconquer algorithm (give a Θ-bound). The input is an array A of size n. You may assume that n is a power of 2. (NOTE: It doesn’t matter what the algorithm does, just analyze its complexity). Assume that the non-recursive function call, bar(A1,A2,A3,n) has cost 3n. Show your work! Next to each statement show its cost when the algorithm is executed on an imput of size n abd give the...
What is the worst-case asymptotic time complexity of the following divide-andconquer algorithm (give a Θ-bound). The input is an array A of size n. You may assume that n is a power of 2. (NOTE: It doesn’t matter what the algorithm does, just analyze its complexity). Assume that the non-recursive function call, bar(A1,A2,A3,n) has cost 3n. Show your work! Next to each statement show its cost when the algorithm is executed on an imput of size n abd give the...
Discrete Math Give a big-Theta estimate for the number of additions in the following algorithm a) procedure f (n: integer) bar = 0; for i = 1 to n^3 for j = 1 to n^2 bar = bar + i + j return bar b) Consider the procedure T given below. procedure T (n: positive integer) if n = 1 return 2 for i = 1 to n^3 x = x + x + x return T(/4) + T(/4) +...