Which of the following codes executes the asymptotically lowest (in terms of the

Question

Which of the following codes executes the asymptotically lowest (in terms of the big- estimate) number of print statements with respect to n?

for i := 1 to n
  for j := 1 to n
    print "Hello"

for i := 1 to n
  for j := 1 to i
    print "Hello"

for i := 1 to n
  for j := 1 to i
    print "Hello"
  for j := i + 1 to n
    print "Hello"

j := 1
for i := 1 to n
  while j < n
    print "Hello"
    j := j + 1

for i := 1 to n
  for j := 1 to n
    print "Hello"

for i := 1 to n
  for j := 1 to i
    print "Hello"

for i := 1 to n
  for j := 1 to i
    print "Hello"
  for j := i + 1 to n
    print "Hello"

j := 1
for i := 1 to n
  while j < n
    print "Hello"
    j := j + 1

Explanation / Answer

The first code snippet is running 2 for loops n times. So, total n*n = n2 print will be called and executed.

For the 4th code snippet, if I convert it in a for lop syntax, it will be same as first code snippet exccept that in inner loop, the condition will be j<n which was j<=n in 1. So, this code will execute print for n*(n-1) times.

The 2nd code snippet will execute this print statement for n*(n+1)/2 times.

The 3rd also if you convert in 1 for loop instead of two inner loops, it turns out to be the same as code snippet 1 as it goes from 1 to n for j. So again it will execute print for n2 time.

So, the answer is: Code snippet 2 will executes the asymptotically lowest (in terms of the big- estimate) number of print statements with respect to n.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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