Analysis of Algorithms and Data Structures: Exercises Solution

This assignment solution addresses exercises from Chapter 4 of "Data Structures and Abstractions with Java," focusing on analyzing algorithms and determining their Big-Oh notation. The solution begins with an introduction to data structures and algorithms, emphasizing their importance in computer science and their role in managing and manipulating data. The assignment covers the analysis of time complexity using Big O notation for different methods, including those involving loops and array manipulations. Specific examples include the time complexity analysis of method1 and private method1, as well as the comparison of two programs (A and B) using Big O notation and logarithmic operations to determine which program runs faster for a given value of n. Furthermore, the solution analyzes the linear search algorithm, discussing its runtime complexity, and differentiating between best-case and worst-case scenarios. The solution provides step-by-step analysis of the algorithm's performance, including operation counts and a complete description of its time complexities. The document concludes by summarizing the importance of understanding algorithm analysis for efficient program design.

Running head: EXERCISES 14, 16, 18
EXERCISES 14, 16, 18
Student
Course
Instructor
Date

1EXERCISES 14, 16, 18.
Introduction:
The algorithms and data structures are vital to computer science. A data structure is the study
of data, its change from structure to another and its description in memory. In programming,
structures of data are used to reserve and arrange data (Chivers & Sleightholme, 2015). The
use of algorithm is to manipulate the data that are stored in those structures. Data structures
are usually based on data types that are abstract. A data type that is abstract is the interface in
java. The examples of data types that are abstract include vehicle, array, and list. Algorithms
are used for computation in mathematics. It is connected with computer science and in
particular with data structures. An algorithm is successive instructions that achieve a job in
limited time (Lafore, 2017). The use of data structures and algorithms are used to solve the
Big O notation problems and time to find out the complexities that are given in the
assignment.
Assignment

2EXERCISES 14, 16, 18.
Answer: In method1 the for loop runs (n-1) times. Therefore, the complexity of method1 is O
(n). In the second method that is the private method1 the for loop runs until the last of the
array that is n. Therefore, the complexity of time of private method1 is O (n).
This also has a best and a worst case.
In best case, the minimum value will be found out in the first step. Then the complexity of
would be f (n) = O (n) + O (1) = O (n)
In worst case, complexity the minimum value will be found out at the last. Therefore, O(n) is
the worst-case complexity for method1 and O (n) for private method1. F (n) = O (n) + O (n)
=O (n2).
Answer: Number of operation required by program A = 1000 X n2
= 500 X 2 X n2
= 2n X 500n
Number of operations required by program B = 2n
Therefore, the time complexity of program A = O (n2)
The run time complexity of program B = O (n)
Now, for comparing the program A and program log needs to be taken at both sides
=>1000 X n2 = 2n
=> log (1000 X n2) = log 2n

3EXERCISES 14, 16, 18.
=>log n2 X log 1000 = n log 2
=> 2 log n X 10 = n [log22 = 1
Log21000= 9.965=10]
Taking the value of n= 219
LHS
2 X log2219 X 10 = 19
=2 X 19 X 10
= 380
Therefore, LHS>RHS
380>19
Therefore, the value of n for which the program A will run or compile faster than program B
is 19. For this value only the program A will run faster than program.
Answer: It is known that linear search is used when the array is not sorted. An approach to
linear search is that the search element has to be differentiated from the left elements of the
array that is from index 0. If the element matches then the index of the element is given as the
output and if it does not then, it returns element not found. The run time complexity of linear
search is O (n) (Vaz et al., 2017). Linear search has two cases of time complexity. One is the

4EXERCISES 14, 16, 18.
Best case another and another is the worst case. The best case complexity of linear search is
O (1) and the worst case complexity of linear search is O (n).
For example:
Linear search (Array arr, integer key)
Integer location = -1;
for ( integer i=0; i< arr.length && location = -1; i++)
If arr[i] = key;
Loc = i;
Return location;
This is an example of a search algorithm known as the liner search algorithm (Das & Khilar,
2013). For finding the best case time complexity and the worst-case time complexity of the
algorithm, the algorithm needs to be analysed
Best case:
Integer location will be executed once. In the for loop (integer i=0) will be executed once.
The next function inside the for loop that is (i<arr.length&& location = -1) will execute 6
times and i++ will be executed 1 time. Then the next function (if arr[i] = key) will be
executed 2 times. (Loc =i) will be executed once and the return loc will be executed once. So
it can be analysed that f (n) = (1+1+6+1+2+1+1= 13), which is a constant. Therefore, the
best-case time complexity for the above program is O (1).
Worst case:
Integer location will be executed once. In the for loop (integer i=0) will be executed once.
The next function inside the for loop that is (i<arr.length&& location = -1) will execute 3n

5EXERCISES 14, 16, 18.
times and i++ will be executed n times. Then the next function (if arr[i] = key) will be
executed 2n times. The (return loc) will be executed once. So it can be analysed that f (n) =
(1+1+1+3n+2n+n) = (6n+3). Therefore, the worst-case run time complexity of linear search
is O (n).
Conclusion
After completing the assignment, it can be seen that analysis of algorithms is very important
to find out the time complexity of programs. Time complexity means minimum time that are
needed to run a program. Big Oh denotes it or O. Time complexity of algorithms consists of
two cases. Best-case complexity is the fewer steps required completing the program and
getting the output. Worst-case complexity means more steps are needed for completing the
program and getting the output.

6EXERCISES 14, 16, 18.
Bibliography
Chivers, I., & Sleightholme, J. (2015). An introduction to Algorithms and the Big O
Notation. In Introduction to Programming with Fortran (pp. 359-364). Springer,
Cham.
Das, P., & Khilar, P. M. (2013). A randomized searching algorithm and its performance
analysis with binary search and linear search algorithms. International Journal of
Computer Science & Applications (TIJCSA), 1(11).
Lafore, R. (2017). Data structures and algorithms in Java. Sams publishing.
Vaz, R., Shah, V., Sawhney, A., & Deolekar, R. (2017, January). Automated big-o analysis
of algorithms. In 2017 International Conference on Nascent Technologies in
Engineering (ICNTE) (pp. 1-6). IEEE.