Lab Overview For this lab you are writing a Java program using a specific algori

Question

Lab Overview

For this lab you are writing a Java program using a specific algorithm AND you are analyzing the run-time analysis for that algorithm
Preparation before Algorithm
Generate an array of 10,000,000 random integers in the range 0-1,000 [feel free to pillage from today’s demo files] – note: if you generate a much smaller number of integers, the average will be further from 500 and the num above might be much higher/lower than half.
Description of Algorithm
The algorithm has two pieces: Average and Number Above Average
Average: First, calculate the average of the elements in the array. (average = sum / n) Do not calculate the sum in the generation of the random numbers. [ you will need a long for the variable that holds the sum ]
Number Above Average : Second, count the number of elements in the array that are greater than the average
Output
Display the average to one decimal, and display the number above the average with commas in the thousands/millions place as show in the sample runs:
Sample Run:
average: 500.2
Num above avg: 4,998,044
Press any key to continue . . .
Another Sample Run:
average: 499.9
Num above avg: 5,001,979
Press any key to continue . . .
Run-time Analysis
In the code, place a comment with an algebraic expression for the algorithm (average and num above average), also place a comment with the Big-O notation for the algorithm.

Grading Rubric
• Java Code for the requested algorithm to calculate the average of the values in the array and the number of elements in the array greater than the average
o Declaration, allocation, and population of array as requested
o Calculation of the average of the elements in the array
o Calculation of the number of elements greater than the average
o Output as requested (see samples)
o Comment in code with name
o following the naming guidelines for Classes and identifier
o proper indenting

-Comment in code for the algebraic expression for the algorithm to determine the average of the values in the array and the number of elements in the array greater than the average

-Comment in code for the Big-O notation for the algorithm to determine the average of the values in the array and the number of elements in the array greater than the average

Explanation / Answer

Interviewers are very interested in whether or not you understand the efficiency of your algorithm, in both running time and space constraints.

Efficiency is usually measured using Big-O analysis, which estimates the worst case scenario of the time it takes for an algorithm to run given an input size of n.

Big-O represents worst case analysis, Big-Theta represents average case, and Big-Omega represents best case. As programmers, we are almost always interested in the worst case scenario, so we'll focus on Big-O analysis.

Big-O analysis is very useful because it allows a programmer to predict an algorithm's running time without having to implement it and run benchmarks.

Since Big-O analysis only cares about the asymptotic running time of the algorithm, it is a rough guess, but the advantage is in not having to worry about the minute details.

Steps for performing Big-O analysis:

NOTE: Some algorithms require Big-O notation using two or more variables: for example, graph algorithm running times are often expressed as O(ve), v for the number of vertices and e for the number of edges.

You should be familiar with the Big-O running time for all of the popular algorithms out there and understand why it takes that long. Keep in mind that the underlying data structure used by an algorithm may change the running time.

O(1) Insertion and deletion for arrays due to random access.
Insertion and deletion of the head element in linked lists.
Insertion and deletion of the root element in heaps. O(log n) Binary search in arrays.
Insertion, deletion, and balancing of binary search trees. O(n) Linked list traversal. O(nlogn) Sorting. O(n^2) O(2^n) Very bad.
NP complete problems are of this class.
Traveling salesman O(n!) Even worse...

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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