Question

An algorithm has a running time like the following: T(n) = T(n-1) + an + b;...

An algorithm has a running time like the following:

T(n) = T(n-1) + an + b; for n> 0 and a, b: the constant T(0) = 0

Determine the complexity of T(n)

Homework Answers

Answer #1

T(n) = T(n-1) + an + b
we need to take an+b in asymptotic.therefore an+b is taken as O(n)
or theta(n)


now equation becomes T(n)=T(n-1)+n
use substitution method:
{T(n) = T(n-1) +n; for n> 0
T(0)=0}


T(n) = T(n-1) +n ---(1)   
T(n-1) = T(n-2) +n-1;
Substitute T(n-1) in equation (1) then
T(n)=T(n-2)+(n-1)+n-----(2)
T(n-2)=T(n-3)+(n-2) substitute T(n-2) in equation(2)then
T(n)=T(n-3)+(n-2)+(n-1)+n---(3)

T(n)=T(n-k)+(n-(k-1))+(n-(k-2))+------+(n-1)+n
assume n-k=0
therefore n=k
T(n)=T(n-n)+(n-n+1)+(n-n+2)+-------+(n-1)+n
T(n)=0+1+2+3+-------+(n-1)+n
T(n)=n(n+1)/2
T(n)=theta(n^2)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
a) Suppose that a particular algorithm has time complexity T(n) = 3 x 2^n, and that...
a) Suppose that a particular algorithm has time complexity T(n) = 3 x 2^n, and that executing an implementation of it on a particular machine takes t seconds for n inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in t seconds? b) Suppose that another algorithm has time complexity T(n) = n^2, and that executing an implementation of it on a particular...
   1)T(n) = 27 T (n/3) + n3 2)Calculate the running time for the following code...
   1)T(n) = 27 T (n/3) + n3 2)Calculate the running time for the following code fragment. Algorithm test int counter, i, j; counter := 0; for (i:= 1; i < n; i*=2) { for (j:= 0; j < i; j++) { counter := counter +1 } } 3)Let f(n) = 2lg 8n + 3 be a function.
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1]...
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1] of real numbers if n = 1 return T[0] else temp ← Test (T[0..n − 2]) if temp ≥ T[n − 1] return temp else return T[n − 1] a. What does this algorithm compute? b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.
Let T(n) be the running time of function do_something. Find the equation of T(n) and find...
Let T(n) be the running time of function do_something. Find the equation of T(n) and find the complexity of T(n) using big-O notation. def do_something(L): s = 0 for x in L: s = s + x print(s) for y in L: s = s + y print(s,x,y) for z in L: s = s + z s = s * 5 return s
Consider the following recursive algorithm. Algorithm Mystery(n) if n=1 then Execute Task A; // Requires Θ(1)...
Consider the following recursive algorithm. Algorithm Mystery(n) if n=1 then Execute Task A; // Requires Θ(1) operations else Mystery(n/3); Mystery(n/3); Mystery(n/3); Execute Task B;  //Requires 2n operations end if Let C(n) be the complexity of Mystery(n). Use the method of backward substitution to determine C(n) in three steps. a) Write the recurrence relation for C(n) including the initial condition. b) Write at least two substitution steps for C(n) and identify the pattern. c) Determine the complexity class of the algorithm in...
1.) the following code fragments give running time analysis (Big Oh). Explain your answer: sum2 =...
1.) the following code fragments give running time analysis (Big Oh). Explain your answer: sum2 = 0; sum5 = 0; for(i=1; i<=n/2; i++) { sum2 = sum + 2; } for(j=1; j<=n*n; j++) { sum5 = sum + 5; } i think it is O(n^2) since big oh finds the order of worst case which is the the second loop being n^2 complexity. but im not sure. 2.) Give an efficient algorithm along with running time analysis to find the...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm that is executed most frequently. Express the number of times it is executed as a function of N. Convert this expression into the Big-O notation. A. For each of the three fragments of code, what is its worst-case time complexity, in the form "O(…)". (Use the given solution to the first problem as a model)                 //----------------- This is a sample problem – solved ------...
Consider the following function : F 1 = 2, F n = (F n-1 ) 2...
Consider the following function : F 1 = 2, F n = (F n-1 ) 2 , n ≥ 2 i. What is the complexity of the algorithm that computes F n using the recursive definition given above. ii. Describe a more efficient algorithm to calculate F n and give its running time.
In class, we have studied the linear time algorithm for selection. In that algorithm, we have...
In class, we have studied the linear time algorithm for selection. In that algorithm, we have used groups of size 5. Suppose we are using groups of size 13. • derive the corresponding recurrence formula. • What is the corresponding time complexity of the algorithm? I found the reccurance relation to be T(n)=O(n)+T(n/13)+T(19n/26), but I am having trouble finding the time complexity. Also I really want to learn this, so a detailed response would be nice. I believe it is...
2. Design a deterministic algorithm to solve the following problem. input: An array A[1...n] of n...
2. Design a deterministic algorithm to solve the following problem. input: An array A[1...n] of n integers. output: Two different indices i and j such that A[i] = A[j], if such indices exist. Otherwise, return NONE. Your algorithm must take O(n log(n)) time. You must describe your algorithm in plain English (no pseudocode) and you must explain why the running time of your algorithm is O(n log(n)).
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT