Write code for a method that uses a loop to compute the sum of all the integers

Question

Write code for a method that uses a loop to compute the sum of all the integers from 1 to N. Perform an algorithm analysis, counting each basic operation (such as assignment and increment++) as one operation. Express your algorithm analysis in Big-O notation. 3. Solution: Method Cost 4. List the order of Big-O terms from lowest to highest. Solution: 5. List the Big-O term for the following sorts and searches: a) Selection sort b) Insertion sort c) Bubble sort d) Quick sort e) Sequential search f) Binary search

Explanation / Answer

3.) Below is the code for computing the sum of all integers from 1 to N

#include<iostream>
using namespace std;

int main(){
int sum = 0;
for(int i=1; i<=N; i++){
  sum = sum +i;
}

}

Algorithm Analysis:

As assignment and increament is computed only one operation. So if you look at the loop

for(int i=1; i<=N; i++){
  sum = sum +i;
}

the above loops runs exactly N number of times . Because for each i from 1 to N it computes one operation i.e.

sum = sum + i;

and when i becomes greater than the N the loop terminates. So as the loop runs for 1 to N i.e. exactly N number of Times so its compexity will be Big-O(N) i.e. O(N).

4.) List of Big-O terms from lowest to Highest

O(logN) < O(N) < O(NlogN) < O(N^C) < O(C^N) < O(N!)      where C is the constant

5.) Compexity of the following is as below

a.) selection sort O(n^2)   : But better than the bubble sort

b) insertion sort: O(n^2) : Better than both insertion and bubble sort

c.) Bubble Sort: O(n^2)

d.) Quick Sort : O(nlogn)

e.) sequentila search:   O(n)

f.) Binary Search: O(logn)

so order will be

binary Search < Sequential Search < Quick Sort < insertion sort < Selection Sort < Bubble Sort

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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