Consider the following code fragment: k = 0 for i = 1 to n do for j = 1 to i do

Question

Consider the following code fragment: k = 0

for i = 1 to n do

for j = 1 to i do

k = k + 2

if j > 5

then k = k + i

A). At the end of this code fragment, what is the value contained in k (expressed as a closed form function of n)?

B) What is the asymptotic running time of the code fragment (as a closed form function of n)?

Justify your answers by explaining and showing your work and/or calculations. For both parts, first express the solution in the form of a summation, and then transform the solution into closed form (no summations in the final answer).

Explanation / Answer

Hi,

I tried the logic as you mentioned.

A)

n k
=========
1 2
2 6
3 12
4 20
5 30

6 48
7 76
8 116
9 170

==========

n^n + n
n^n + n^2

But i am not sure of result.

b)

since there are two for loops....O(n2)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.