Can anyone help me with this Discrete Mathematics problem? I am finding it diffi

Question

Can anyone help me with this Discrete Mathematics problem? I am finding it difficult to understand

*For each of these problems give the best upper bound you can for the running time, using a simple function of smallest order.*

1.) Give a big-O estimate for the number of additions used in this segment of an algorithm.

t:=0

for i:= 1 to n

for j:=1 to n

t:= t+i+j

2.) Give a big-O estimate for the number of operations, where an operation is a comparison or a multiplication, used in this segment of an algorithm (ignoring comparisons used to test the conditions in the for loops, where a1, a2, ..., an are positive real numbers).

m := 0

for i := 1 to n

for j := i + 1 to n

m := max(aiaj,m)

Explanation / Answer

for i:= 1 to n

for j:=1 to n

t:= t+i+j

when

i =1, inner loop runs n times

i =2, inner loop runs n times

i =3, inner loop runs n times

.

.

i =n, inner loop runs n times

Total number of times runs

= n + n + n + .... n times

= n * n

= n2

T.C = O(n2)

m := 0

for i := 1 to n

for j := i + 1 to n

m := max(aiaj,m)

when

i =1, inner loop runs 2 times

i =2, inner loop runs 3 times

i =3, inner loop runs 4 times

.

.

i =n, inner loop runs n+1 times

Total number of times runs

= 2 + 3 + 4 ... n + 1

= (1 + 1 + 1 + ..n times) + (1 + 2+ 3 . . . . + n)

= n + (n * ( n + 1) /2)

= n + (n2 + n) / 2

= O ( n2)

for i:= 1 to n

for j:=1 to n

t:= t+i+j

when

i =1, inner loop runs n times

i =2, inner loop runs n times

i =3, inner loop runs n times

.

.

i =n, inner loop runs n times

Total number of times runs

= n + n + n + .... n times

= n * n

= n2

T.C = O(n2)

m := 0

for i := 1 to n

for j := i + 1 to n

m := max(aiaj,m)

when

i =1, inner loop runs 2 times

i =2, inner loop runs 3 times

i =3, inner loop runs 4 times

.

.

i =n, inner loop runs n+1 times

Total number of times runs

= 2 + 3 + 4 ... n + 1

= (1 + 1 + 1 + ..n times) + (1 + 2+ 3 . . . . + n)

= n + (n * ( n + 1) /2)

= n + (n2 + n) / 2

= 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.