This first assignment is an analysis of algorithms and understanding growth func
ID: 3883841 • Letter: T
Question
This first assignment is an analysis of algorithms and understanding growth functions using Big-Oh notation.
1.Explain what O(1) means.
2.If the Big-O calculation for a code segment is O(2n), what do you conclude about the code segment? Why?
3.How many times will the following code print out Hello World (in terms of the length of the array)?
for(int i = 0; i < array.length; i++) {
for(int j = 0; j < array.length; j++) {
for(int k = 0; k < array.length; k++) {
System.out.println(“Hello World!”);
}
}
}
4.What is the complexity of the following code (in terms of the length of the array), assuming someMethod has a complexity of O(1)?
for(int i = 0; i < array.length; i++)
for(int j = 0; j < array.length; j++)
someMethod(array[j]);
5.What is the complexity of the following code (in terms of the length of the array)?
for(int i = 0; i < 5; i++)
System.out.println(array[i]);
6.Why do we do algorithm analysis to compare algorithms?
7.Write a code segment that represents an order, for each of the following orders.
Log N
N
N Log N
N
N^2
N^3
2^N
8.How can we be certain (validate) that the code segments in the previous question are the correct order?
Explanation / Answer
1. O(1) means constant time.
For Example-
int i=0; ---- O(1)
if(i==0){ ---- O(1)
int z=i+1; ---- O(1)
}
Every statement here takes constant time.
2. Complexity O(2n) means the algorithm is linear i.e O(n). Theoretically, there is not
much difference between O(2n) and O(n) as both means linear growth.
3. Each loop will iterate array.length times, for three loops (array.length)*(array.length)*(array.length).
So, "Hello world!" will be printed (array.length)^3.
4. Let, n=array.length, both for loop will be iterated n times, so complexity will be O(n^2).
5.Length of the array here is 5, complexity will be O(5).
6.We do algorithm analysis so that we can understand the time and memory usage by algorithms and
can optimize them to reduce time and space complexity. As algorithm with high complexity can decrease
programs speed and efficiency and eventually can lead to bad performance.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.