# CSE 222/505 – Homework 2

\$30.00

## Description

Q1:
Give running times of each of the algorithms in proper notations. Explain your answers.
1.
2.
Q2:
1. What does the function do?
2. Give the best-case and worst-case running times of the algorithm in Ɵ notation.
Q3:
Prove that the running time of an algorithm is Ɵ(g(n)) if and only if its worst-case running
time is O(g(n)) and its best-case running time is Ω(g(n)).
Q4:
1. Express insertion sort as a recursive procedure.
2. Write a recurrence for the worst-case running time of the procedure. Explain your
3. Solve the recurrence. Give detailed answer.
Q5:
Indicate giving detailed explanation whether f(n) = O(g(n)), f(n) = Ω(g(n)) or f(n) = Ɵ(g(n)) for
the following:
1. 𝑓(𝑛) = 𝑛
0.1
, 𝑔(𝑛) = (log 𝑛)
10
2. 𝑓(𝑛) = 𝑛!, 𝑔(𝑛) = 2
𝑛
3. 𝑓(𝑛) = (log 𝑛)
log𝑛
, 𝑔(𝑛) = 2
(log2 𝑛)
2
Q6:
Rearrange your Homework 1 code using Array, Array List, and Linked List structures. Analyze
performance analysis method. Also, write detailed analysis results in your report.
RESTRICTIONS:
– Can be only one main class in project
– Don’t use any other third part library
GENERAL RULES:
– For any question firstly use course news forum in moodle, and then the contact TA.
– You can submit assignment one day late and will be evaluated over twenty percent (%20).
– Register github student pack and create private project and upload your projects into github.
TECHNICAL RULES:
– Use given CSE222-VM to develop and test your homeworks (your code must be working on
– Implement clean code standarts in your code;
o Classes, methods and variables names must be meaningful and related with the
functionality.
o Your functions and classes must be simple, general, reusable and focus on one topic.
o Use standart java code name conventions.
REPORT RULES:
– Add all javadoc documentations for classes, methods, variables …etc. All explanation must be
meaningful and understandable.
– You should submit your homework code, javadoc and report to Moodle in a
studentid_hw#.tar.gz file.
– Use the given homework format including selected parts:

Detailed system requirements
The Project usecase diagrams (extra points)
Class diagrams
Other diagrams
Problem solutions approach x
Test cases x
Running command and results x