This documentation is part of the Critical Thinking 3 Assignment from CSC400: Data Structures and Algorithms at Colorado State University Global. It consists of a series of exercises designed to demonstrate the principles of asymptotic analysis. Asymptotic analysis uses the Big-Oh notation.
“In computer science, the Big-Oh notation is used to describe the time complexity or space complexity of algorithms (Geeks for Geeks, 2024). Mathematically, it defines the upper bound of an algorithm’s growth rate, known as the asymptotic upper bound, and is denoted as 𝑓(𝑛) is 𝑂(𝑔(𝑛)) or 𝑓(𝑛) ∈ 𝑂(𝑔(𝑛)), pronounced 𝑓(𝑛) is Big-Oh of 𝑔(𝑛). The term “asymptotic” refers to the behavior of the function as its input size 𝑛 approaches infinity. In the context of computer science, it describes the worst-case scenario for time complexity or space complexity. For example, an algorithm with 𝑂(𝑛²) time complexity will grow much faster than one with 𝑂(𝑛) as the input size increases, with n representing the number of primitive operations. Primitive operations are low-level instructions with a constant execution time.” (Ricciardi, 2024. Post)
Definition of Big-Oh:
Let f(n) and g(n) be functions mapping positive integers to positive real numbers. We say that f(n) ∈ O(g(n)) if there is a real constant c > 0 and an integer constant n0 ≥ 1 such that
f(n) ≤ c⋅g(n) , for n ≥ n0
(Carrano & Henry, 2018)
The Assignment Direction: Complete the following exercises. For each exercise, show your work and all the steps taken to determine the Big-Oh for each problem. Partial points cannot be awarded without showing work.
Exercise 1
What is the Big-Oh of the following computation?
int sum = 0;
for (int counter = n; counter > 0; counter = counter - 2)
sum = sum + counter;
Exercise 2
Suppose your implementation of a particular algorithm appears in Java as follows:
for (int pass = 1; pass <= n; pass++)
{
for(int index = 0; index < n; index++)
{
for(int count = 1; count < 10; count++)
{
. . .
} //end for
} // end for
} //end for
The algorithm involves an array of “n” items. The previous code shows only the repetition in the algorithm, but it does not show the computations that occur within the loops. Those computations, however, are independent of “n.” What is the order of the algorithm?
Exercise 3
Consider two programs, A and B. Program A requires 1000 x n² operations and Program B requires 2n operations.
For which values of n will Program A execute faster than Program B?
Exercise 4
Consider an array of length “n” containing unique integers in random order and in the range 1 to n + 1.
For example, an array of length 5 would contain 5 unique integers selected randomly from the integers 1 through 6. Thus the array might contain 3 6 5 1 4. Of the integers 1 through_ 6_, notice that 2 was not selected and is not in the array.
Write Java code that finds the integer that does not appear in such an array.
Explain the Big-Oh in your code.
My notes:
- Each exercise starts on a new page.
- 𝑔(𝑛) is the number of primitive operations.
- The summation properties of a constant
Exercise 1
What is the Big-Oh of the following computation?
int sum = 0;
for (int counter = n; counter > 0; counter = counter - 2)
sum = sum + counter;
In this exercise 𝑔(𝑛) is the number of primitive operations.
Step 1: Understanding the code
The ‘sum’ variable initializes to ‘0’.
The ‘counter’ loop iterates from ’n’ to ‘1’ inclusive. Note that all the variables and constants in the loop are integers.
- The ‘counter’ variable initializes to ‘n’.
- The ‘counter’ variable is compared to ‘0’, the loop iterates as long as ‘counter’ is greater than ‘0’.
- The ‘counter’ variable is post-decremented by ‘2’, this means that the ‘counter’ is compared to ‘0’ before being decremented.
- The ‘sum’ variable is incremented by the value of the ‘counter’ variable in each iteration of the for-loop until the ‘counter’ is less than or equal to ‘0’.
If ‘n = 10’
1st iteration ‘counter = 10’ and ‘sum = 0 + 10 = 10’
2nd iteration ‘counter = 8’ and ‘sum = 10 + 8 = 18’
3rd iteration ‘counter = 6’ and ‘sum = 18 + 6 = 24’
4th iteration ‘counter = 4’ and ‘sum = 24 + 4 = 28’
5th iteration ‘counter = 2’ and ‘sum = 28 + 2 = 30’
The number of iterations is 𝑛/2
If ‘n = 11’
1st iteration ‘counter = 11’ and ‘sum = 0 + 11 = 11’
2nd iteration ‘counter = 9’ and ‘sum = 11 + 9 = 20’
3rd iteration ‘counter = 7’ and ‘sum = 20 + 7 = 27’
4th iteration ‘counter = 5’ and ‘sum = 27 + 5 = 32’
5th iteration ‘counter = 3’ and ‘sum = 32 + 3 = 35’
6th iteration ‘counter = 1’ and ‘sum = 32 + 1 = 36’
The number of iterations is (𝑛+1)/2
Step 2: Counting the number of iterations
The for-loop will iterate as long as the ‘counter > 0’, the ‘counter is initialized to ’n’, and it is decremented by ‘2’.
If 𝑘 is the number of iterations, then the last iteration would occur when 𝑛 — 2𝑘 ≤ 0. Solving for 𝑘, 𝑘 ≥ 𝑛/2 . Using the examples above of ‘n = 10’ and ‘n = 11’, we can say that 𝑘 = 𝑛/2 when 𝑛 is even and k = (𝑛+1)/2 when 𝑛 is odd.
Justification:
An odd number is an integer of the form 𝑛 = 2𝑐 + 1, where 𝑐 is an integer.
Then 𝑘 = (2𝑐+1+1)/2 = (2/2) 𝑐 + (2/2) = 𝑐 + 1.
An even number is an integer of the form 𝑛 = 2𝑐, where 𝑐 is an integer.
Then 𝑘 = (2𝑐)/2 = (2/2) 𝑐 = 𝑐
If 𝑐 = 5
Then 𝑛𝑒𝑣𝑒𝑛 = 2∗5 = 10 and 𝑘𝑒𝑣𝑒𝑛 = 𝑛_𝑒𝑣𝑒𝑛/2 = 5 = 𝑐
And 𝑛𝑜𝑑𝑑 = 2∗5+1 = 11 𝑎𝑛𝑑 𝑘𝑜𝑑𝑑 = (11+1)/2 = 12/2 = 6 = 𝑐+1
Step 3: Number of primitive operations 𝑔(𝑛) per instruction
The ‘sum’ variable initializes to 0, it is executed only once,
𝑔₁(𝑛) = 1.
The ‘counter’ variable initializes to n by the for-loop statement this is executed only once,
𝑔₂(𝑛) = 1.
The ‘counter’ variable is compared to ‘0’, this is executed in each iteration of the loop, and the number of iterations is 𝑘𝑒𝑣𝑒𝑛 = 𝑛𝑒𝑣𝑒𝑛/2 , then 𝑔₃(𝑛𝑒𝑣𝑒𝑛) = 𝑛𝑒𝑣𝑒𝑛/2; and 𝑘𝑜𝑑𝑑 = (𝑛𝑜𝑑𝑑+1)/2, then
𝑔₃(𝑛𝑜𝑑𝑑) = (𝑛𝑜𝑑𝑑+1)/2
The ‘counter’ is post-decremented by ‘2’, this is done after each iteration of the loop and the comparison of ‘counter’ to ‘0’returns true, the number of iterations is 𝑘𝑒𝑣𝑒𝑛 = 𝑛𝑒𝑣𝑒𝑛/2, then 𝑔₄(𝑛𝑒𝑣𝑒𝑛) = 𝑛𝑒𝑣𝑒𝑛/2 ; and 𝑘𝑜𝑑𝑑 = (𝑛𝑜𝑑𝑑+1)/2, then
𝑔₄(𝑛𝑜𝑑𝑑) = (𝑛_𝑜𝑑𝑑+1)/2
The ‘sum’ variable is incremented by the value of the ‘counter’ variable in each iteration of the for-loop until the ‘counter’ is less than or equal to ‘0’, then the number of times this instruction will be executed is the number of iterations 𝑘𝑒𝑣𝑒𝑛 = 𝑛𝑒𝑣𝑒𝑛/2, then 𝑔₅(𝑛𝑒𝑣𝑒𝑛) = 𝑛𝑒𝑣𝑒𝑛/2 ; and 𝑘𝑜𝑑𝑑 = (𝑛𝑜𝑑𝑑+1)/2, then
𝑔₅(𝑛𝑜𝑑𝑑) = (𝑛𝑜𝑑𝑑+1)/2
Step 4: The total of primitive operations
If 𝒏 is even, 𝒌 = 𝒏/𝟐
𝑔(𝑛) = 𝑔₁(𝑛) + 𝑔₂(𝑛) + 𝑔₃(𝑛) + 𝑔₄(𝑛) +𝑔₅(𝑛)
𝑔(𝑛) = 1 + 1 + 𝑘 + 𝑘 + 𝑘 = 1 + 1 + 𝑛/2 + 𝑛/2 + 𝑛/2
𝑔(𝑛) = 2 + (3/2)𝑛
If 𝒏 is odd, 𝒌 = (𝒏-𝟏)/𝟐
𝑔(𝑛) = 𝑔₁(𝑛) + 𝑔₂(𝑛) + 𝑔₃(𝑛) + 𝑔₄(𝑛) +𝑔₅(𝑛)
𝑔(𝑛) = 1 + 1 + 𝑘 + 𝑘 + 𝑘 = 1 + 1 + (𝑛+1)/2 + (𝑛+1)/2 + (𝑛+1)/2 = 2/2 + 2/2 + 1/2 + 1/2 + 1/2 + 𝑛/2 + 𝑛/2 + 𝑛/2
𝑔(𝑛) = 7/2 + (3/2)𝑛
Step 5: The Big-Oh notation
By the definition of the Big-Oh notation, 𝑂(𝑔(𝑛)).
If 𝑛 is even, with 𝑔(𝑛) = 2 + (3/2)𝑛 then the asymptotic complexity is 𝑂(𝑛)
Justification:
2 + (3/2)𝑛 ≤ 𝑐𝑛, for 𝑐 = 4/2 + 3/2 = 7/2 , when 𝑛 ≥ 𝑛₀ = 2 and 𝑛 is even.
If 𝑛 is odd, with 𝑔(𝑛) = 7/2 + (3/2)/𝑛 then the asymptotic complexity is 𝑂(𝑛)
justification:
2 + (3/2)𝑛 ≤ 𝑐𝑛, for 𝑐 = 4/2 + 3/2 = 7/2 , when 𝑛 ≥ 𝑛₀ = 1 and 𝑛 is odd.
When 𝑛 is even Big-Oh is 𝑂(𝑛) and when 𝑛 is even Big-Oh 𝑂(𝑛), thus:
The Big-Oh of the computation is 𝑂(𝑛)
In conclusion, the asymptotic analysis shows that the complexity of the algorithm is directly proportional to the size of the input n, indicating a linear growth rate. O(n) represents a linear type of complexity.
Exercise 2
Suppose your implementation of a particular algorithm appears in Java as follows:
for (int pass = 1; pass <= n; pass++)
{
for(int index = 0; index < n; index++)
{
for(int count = 1; count < 10; count++)
{
. . .
} //end for
} // end for
} //end for
The algorithm involves an array of “n” items. The previous code shows only the repetition in the algorithm, but it does not show the computations that occur within the loops. Those computations, however, are independent of “n.” What is the order of the algorithm?
Note that the order of an algorithm refers to its “time complexity” or Big-Oh notation. Below is the time complexity analysis of the code above.
Step 1: Understanding the code
The outer loop (‘pass’) itenerates from ‘1’ to ’n’ inclusive. Note that all the variables and constants in the loop are integers.
- The ‘pass’ variable initializes to ‘1’.
- The ‘pass’ variable is compared to ’n’, the loop iterates as long as ‘pass’ is less than or equal to ‘n’.
- The ‘pass’ variable is post-incremented by ‘1’, this means that the ‘pass’ variable is compared to ’n’ before being incremented.
The middle loop (‘index’) itenerates from ‘0’ to ’n’ exclusive. Note that all the variables and constants in the loop are integers, - The ‘index’ variable initializes to ‘0’.
- The ‘index’ variable is compared to ’n’, the loop iterates as long as ‘index’ is less than ‘n’.
- The ‘index’ variable is post-incremented by ‘1’, this means that the ‘pass’ variable is compared to ’n’ before being incremented.
- The inner loop (‘count’) itenerates from ‘1’ to ‘10’ exclusive. Note that all the variables and constants in the loop are integers.
- The ‘count’ variable initializes to ‘1’.
- The ‘count’ variable is compared to ‘10’, the loop iterates as long as ‘count’ is less than ‘10’.
- The ‘count’ variable is post-incremented by ‘1’, this means that the ‘count’ variable is compared to ‘10’ before being incremented.
Step 2: Counting the number of iterations
The outer loop will iterate as long as ‘pass’ is less than or equal to ’n’, and it is post-incremented by ‘1’, starting at ‘pass = 1’. If is the number of iterations:
Thus, the loop iterates 𝑛 times. However, since the loop is nested within the outer loop, it iterates a total of 𝑛 ∙ 𝑛 = 𝒏² times.
The inner loop will iterate as long as ‘count’ is strictly less than ‘10’, and it is post-incremented by ‘1’, starting at ‘pass = 1’.
If 𝑘 is the number of iterations:
The Java code:
/**
* Finds the missing number
*
* @param array The array of unique integers with one integer missing.
* @param n The length of the array
* @return The missing integer
*/
public static int missingNum(int[] array, int n) {
// The expected sum of integers from 1 to n+1
int expectedSum = (n + 1) * (n + 2) / 2;
int actualSum = 0;
// The actual sum of the numbers in the array
for (int i = 0; i < n; i++) {
actualSum += array[i];
}
return expectedSum - actualSum;
}
Step 1: Understanding the code
The ‘expectedSum’ variable initializes to ‘(n + 1) * (n + 2) / 2’.
The ‘actualSum’ variable initializes to ‘0’.
The ‘array’ loop iterates through from the ‘0’ to the ’n’ exclusive. Note that all the variables and constants in the loop are integers.
- The ‘i’ variable initializes to ‘0’.
- The ‘i’ variable is compared to ’n’, the loop iterates as long as ‘i’ is lesse than ‘n’.
- The ‘i’ variable is incremented by ‘1’, this means that the ‘i’ is compared to ’n’ before being incremented.
- The ‘atualSum’ variable is incremented by the value of the ‘arrau[i]’ variable in each iteration of the for-loop until the ‘i’ is equal to or more than ‘n’.
The function returns ‘expectedSum — actualSum’
Step 2: Counting the number of iterations in the array loop
The array loop will iterate as long as ‘i’ is less ’n’, and it is post-incremented by ‘1’, starting at ‘i = 0’.
If 𝑘 is the number of iterations:
on September 18, 2024.
SOCIAL SHARE CARD GENERATOR