CSIT 254 BCC Java Programming Data Structure Project Worksheet

CSIT 254 – Data Structure Lab 01.5 – Run-Time Combined – Front and Back!!!!
Name 1 _______________________________
Name 2 _______________________________
1. Each of the following are formulas for the number of operations for some algorithm. Express the
big-O notation for each of the formulas [ Example: O(n2) ] (30 points)
Formula
Big O notation
4n + 1
O( n )
½ n + 12
3+3
4n + n2 + 6
4n + 2n + 2n + 1
3n3 + 10
2. Given an array of ints data, where n is data.length and is large, and target is an int, consider the
following algorithm:
int count = 0;
for (int i = 0; i < n; i++) { if (data[i] == target) { count++; } } a) determine the formula for the number of operations – precise method/worst case (15 points) Formula: b) write the big-O notation for the number of operations from a) (5 points) Big-O: c) determine the formula for the number of operations – precise method/best case (15 points) Formula: d) write the big-O notation for the number of operations from c) (5 points) Big-O: Submit this on paper to the instructor CSIT 254 – Data Structure Lab 01.5 – Run-Time Combined – Front and Back!!!! Name 1 _______________________________ Name 2 _______________________________ 3. Given an array of ints data, where n is data.length and is large, and target is an int, consider the following algorithm: int count = 0; for (int i = 0; i < n; i++) { if (data[i] == target) { count++; } } a) Explain in full English sentences the scenario for the worst case (15 points) b) Explain in full English sentences the scenario for the best case (15 points) Submit this on paper to the instructor