1 answer

1. Analyze the running time of the following algorithm and write it using ( notation. You...

Question:

1. Analyze the running time of the following algorithm and write it using ( notation. You must show detailed calculation/deri

1. Analyze the running time of the following algorithm and write it using ( notation. You must show detailed calculation/derivation of your running time along with table to get marks. int sum = 0; for (int i=n; i)=1; i=i/2) { for (int j=1; j<=i; j*=2) { sum+=i*j; } }

Answers

1.

The 2 for loops in the code segment are not independent and so the product rule cannot be used to compute the time complexity.

Since both i loop and j loop are dependent upon each other, let's analyze how both the loops work using the following table :

Value of i n n/2 n/4 1
j loop runs for log n times log ( n / 2 ) times log ( n / 4 ) times log ( 1 ) times

Let the running time of the algorithm be represented as T(n).

So, the time complexity is calculated as :

T(n) = Sum of the total number of times j loop runs

= log n +  log ( n / 2 ) +  log ( n / 4 ) + .................... log ( 1 )

= log ( n * n /2 * n / 4 .......... 1 ) + 0 [ logarithmic property ]

<= log ( n^n)

<= n log n

So,

T(n) = Θ(n log n)

Hence, the running time of the given algorithm is Θ(n log n).

.

Similar Solved Questions

1 answer
What are common barriers to interpersonal communication? What strategies can nurses employ to overcome those barriers?...
What are common barriers to interpersonal communication? What strategies can nurses employ to overcome those barriers? Please provide a personal example of a time where you faced an interpersonal communication barrier during your bedside nursing career....
1 answer
A academic tutor wants to assess whether her remedial tutoring has been effective for her five...
A academic tutor wants to assess whether her remedial tutoring has been effective for her five students. She decides to conduct a related samples t-test and records the following grades for students prior to and after receiving her tutoring. Tutoring Before After 2.4 3.1 2.5 2.9 3.0 3.5 2.9 3.1 2.7 ...
1 answer
Of these three types of light, which has the longest wavelength? O visible light O ultraviolet...
of these three types of light, which has the longest wavelength? O visible light O ultraviolet light infrared light O All three have the same wavelength. QUESTION 4 Of these three types of light, which has the most energy per photor O visible light O ultraviolet light O infrared light All three have...
1 answer
DeShannon Company applies overhead to production based on direct labour hours. Data for the most current...
DeShannon Company applies overhead to production based on direct labour hours. Data for the most current year are as follows: Estimated Actual Direct labour hours 582673 560105 Manufacturing overhead ? S697595 The manufacturing overhead for the past year was over-applied by $35828. What was the esti...
1 answer
Question 11 4 pts The projected sales (in thousands) of a small company over the next...
Question 11 4 pts The projected sales (in thousands) of a small company over the next 10 years are approximated by the function: S(x)=0.07x4-0.05x3 +2x2 +7x+62. Find the first derivative: (a) 0.14x3 -0.15x2 + 4x +7 (b) 0.28x3 -0.15x2 +4x (c) 0.14x3 -č. 1x2 +4x +7 (d) 0.14x3 -0.15x2 +4x (e)0.28x...
1 answer
Portsmouth Company makes upholstered furniture. Its only variable cost is direct materials. The demand for the...
Portsmouth Company makes upholstered furniture. Its only variable cost is direct materials. The demand for the company's products far exceeds its manufacturing capacity. The bottleneck (or constraint) In the production process is upholstery labor-hours. Information concerning three of Portsmouth...
1 answer
B С Trial Balance December 31 Credit Debit $5,700 1,400 11,100 3,800 27,400 А 1 2...
B С Trial Balance December 31 Credit Debit $5,700 1,400 11,100 3,800 27,400 А 1 2 3 4 Cash 5 Accounts receivable 6 Notes receivable 7 Prepaid services 8 Office equipment 9 Accounts payable 10 Unearned ticket revenue 11 Common stock 12 Dividends 13 Ticket revenue 14 Rental revenue 15 Sala...
1 answer
What is the distance between #(-7,5)# and #(2,12)#?
What is the distance between #(-7,5)# and #(2,12)#?...
1 answer
A technician wraps wire around a tube of length 34 cm having a diameter of 8.1...
A technician wraps wire around a tube of length 34 cm having a diameter of 8.1 cm. When the windings are evenly spread over the full length of the tube, the result is a solenoid containing 555 turns of wire. (a) Find the self-inductance of this solenoid. mH (b) If the current in this solenoid incre...
1 answer
7. Given a buffer solution of sodium hydrogen carbonate (NaHCO3) and sodium carbonate (Na2CO3). a. Calculate...
7. Given a buffer solution of sodium hydrogen carbonate (NaHCO3) and sodium carbonate (Na2CO3). a. Calculate the pH of this buffer solution when 0.100M sodium hydrogen carbonate (NaHCO3) and 0.100M sodium carbonate (Na2CO3). (Ka = 7.94 x 10-7) b. Calculate the new pH value of this buffer solution wh...
1 answer
Which requirement for qualified property does the following example fail? example Jane purchased a desk for...
which requirement for qualified property does the following example fail? example Jane purchased a desk for a business use on May 11th 2008 and began using it immediately she used the desk and her business for all of 2019 and it was available for use at the year tax year...
1 answer
Quantum mechanics number 4 only. Useful information: The resolving power of a microscope is directly proportional...
quantum mechanics number 4 only. Useful information: The resolving power of a microscope is directly proportional to the wavelength. For relativistic conditions Epem K E-me, where m is the rest mass. For the electron m 0.511 MeV. Starting at rest find over what potential do you need to accelerate th...
1 answer
3 simple steps toward weight loss
3 simple steps toward weight loss...
1 answer
Carefully analyze the movie "Miss Evers' Boys" Tuskegee film; What was the purpose of the study?...
Carefully analyze the movie "Miss Evers' Boys" Tuskegee film; What was the purpose of the study? That is, why was the study authorized by the United States Public Health Service?...
1 answer
Please let me know if you can not read the numbers 2700 For Prepaid Insurance and...
Please let me know if you can not read the numbers 2700 For Prepaid Insurance and Depreciation Expense 3250 Accounts Receivable - Prepaid Rent Prepaid Insurance BB 95.40 BB 30,00 15,000 BB 2,700 Prepaid Supplies BE 400 95420 - 1000 25000 2.200 120 Equipment Accumulated Depreciation Accrued Interes...
1 answer
How do you find the projection of u=<4,8> onto v=<-1,2>?
How do you find the projection of u=<4,8> onto v=<-1,2>?...
1 answer
A local real estate investor in Orlando is considering three alternative investments; a motel, a restaurant,...
A local real estate investor in Orlando is considering three alternative investments; a motel, a restaurant, or a theater. Profits from the motel or restaurant will be affected by the availability of gasoline and the number of tourists; profits from the theater will be relatively stable under any co...