What are the running times of the following four loops? Briefly justify your answers. (in all cases, assume that n is sufficiently large if it needs to be assumed for the problem to make sense).   1) for (int i = 0; i < n*n; i++) { sum += i; }       2) for (int i = 0; i*i < n; i++) {      sum += i; }     3) for (int i = n*n; i > 1; i /= 2) {      if (i > 16) {            sum += i;      } }     4) for (int i = 0; i < n; i++) {      for (int j = 0; j < n; j++) {            for (int k = j+1; k < n; k++) {                 sum += i*j*k;

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

What are the running times of the following four loops? Briefly justify your answers. (in all cases, assume that n is sufficiently large if it needs to be assumed for the problem to make sense).

 

1) for (int i = 0; i < n*n; i++) {

sum += i;

}

 

 

 

2) for (int i = 0; i*i < n; i++) {

     sum += i;

}

 

 

3) for (int i = n*n; i > 1; i /= 2) {

     if (i > 16) {

           sum += i;

     }

}

 

 

4) for (int i = 0; i < n; i++) {

     for (int j = 0; j < n; j++) {

           for (int k = j+1; k < n; k++) {

                sum += i*j*k;

           }

     }

Expert Solution
steps

Step by step

Solved in 2 steps with 11 images

Blurred answer
Knowledge Booster
Matrix multiplication
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education