for i 1 to j Statements in the body of the inner loop, none containing branching
ID: 3703163 • Letter: F
Question
for i 1 to j Statements in the body of the inner loop, none containing branching statements that lead outside the loop COT 3100 Intro. To Discrete Structures Problem 1: Assume that n is a positive integer. For each of the following algorithm segments, how many times will the Innermost loop be lterated when the algorithm segment is implemented and run? (5 points for each) 1. for k:- 1 to n next i next next k for1 to k 6, for k := 1 to n [Statements in the body of the inner loop, none containing branching statements thet lead outside the loop for1 to k- 1 fori: 1 toj-1 next Statements in the body of the inner loop, none containing branching statements that lead outside the loop next k 2. for k := 1 to n-1 next i for1 to k+ 1 next [Statements in the body of the inner loop, none containing branching statements thet lead outside the loopl next k Problem 2 (10 points): Suppose a sequence satisfies the below given recurrence relation and initial conditions. Find an explicit formula for the next next k ak 2132 for all integers kz 2 ao-1,a,-2 3. for k:1 to n-1 for jk+1 to n [Statements in the body of the inner branching statements that lead outside the loop none containing Problem 3 (10 points Suppose a sequence satisfies the below given recurrence relation and initial conditions. Find an explicit formula for the sequence next a,-6ae-1-9@g-2 for all integers k?2 ao-1, a,-3 next k 4. for k:1 to n 1 for k to n Statements in the body of the inner loop, none containing branching statements that lead outside the loop next j next k 5. fork:- 1 to n for 1 to kExplanation / Answer
As per Chegg policy, I am answering only first 4 subparts of first Question. Kindly upload the remaining questions again in order to know their solution.
Problem 1:
1.) Since inner loop is dependent on the values of outer loop variable, k. For k = 1, it runs 1 time, for k=2, it runs 2 times, and so on. So in total, it runs for 1+2+..+n = n*(n+1)/2 times.
2.) Since inner loop is dependent on the values of outer loop variable, k. For k = 1, it runs 2 times, for k=2, it runs 3 times, and so on. So in total, it runs for 2+..+n = {(n*(n+1)/2) - 1} times.
3.) Since inner loop is dependent on the values of outer loop variable, k. For k = 1, it runs n-1 times, for k=2, it runs n-2 times, and so on. So in total, it runs for n-1 + .. + 2 = (n*(n+1)/2) - n - 1= (n+1)*(n-2)/2 times.
4.) Since inner loop is dependent on the values of outer loop variable, k. For k = 1, it runs n times, for k=2, it runs n-1 times, and so on. So in total, it runs for n + n-1 + ...+ 2 = (n*(n+1)/2) -1 times.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.