Scribd
Upload
3 views4 pages

Array Complexity

The document contains a series of programming questions focused on analyzing the time complexity of various Java functions that manipulate arrays. Each question requires deriving exact summations, justifying answers, and providing complexity in Big-O, Big-Theta, and Big-Omega notation where applicable. The questions cover nested loops, logarithmic behavior, and recursive functions, emphasizing the importance of understanding algorithm efficiency.

Uploaded by

aryaninformal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views4 pages

Array Complexity

The document contains a series of programming questions focused on analyzing the time complexity of various Java functions that manipulate arrays. Each question requires deriving exact summations, justifying answers, and providing complexity in Big-O, Big-Theta, and Big-Omega notation where applicable. The questions cover nested loops, logarithmic behavior, and recursive functions, emphasizing the importance of understanding algorithm efficiency.

Uploaded by

aryaninformal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Data Structures Using Java

Instructions:

1. Let n be the size of the array unless otherwise stated.

2. Derive exact summation wherever possible.

3. Write complexity in Big-O, Big-Theta and Big-Omega where applicable.

4. Justify all answers clearly.

Question 1:
void q1(int[] arr) {
for(int i = 0; i < [Link]; i++) {
for(int j = i; j < [Link]; j++) {
[Link](arr[j]);
}
}
}
Derive exact summation and final time complexity.

Question 2:
void q2(int[] arr) {
for(int i = 0; i < [Link]; i++) {
for(int j = 0; j < [Link]; j += 2) {
[Link](arr[j]);
}
}
}
Find time complexity. Is it O(n²/2)? Justify.

Question 3:
void q3(int[] arr) {
for(int i = [Link] - 1; i >= 0; i--) {
for(int j = i; j >= 0; j--) {
[Link](arr[j]);
}
}
}
Derive total number of iterations and complexity.

Question 4:
void q4(int[] arr) {
for(int i = 1; i < [Link]; i *= 2) {
for(int j = 0; j < [Link]; j++) {
[Link](arr[j]);
}
}
}
Find time complexity using logarithmic analysis.

Question 5:
void q5(int[] arr) {
for(int i = 0; i < [Link]; i++) {
for(int j = 0; j < i * i; j++) {
[Link](arr[i]);
}
}
}
Derive summation and final complexity.

Question 6:
void q6(int[] arr) {
for(int i = 0; i < [Link]; i++) {
for(int j = 1; j < [Link]; j *= 2) {
[Link](arr[i]);
}
}
}
Find time complexity and explain interaction between loops.

Question 7:
void q7(int[] arr) {
for(int i = 0; i < [Link]; i++) {
for(int j = 0; j < [Link] - i; j++) {
for(int k = 0; k < j; k++) {
[Link](arr[k]);
}
}
}
}
Derive full summation and prove final complexity.

Question 8:
void q8(int[] arr) {
int n = [Link];
while(n > 0) {
for(int i = 0; i < n; i++) {
[Link](arr[i]);
}
n = n / 2;
}
}
Find time complexity and show geometric series expansion.

Question 9:
void q9(int[] arr) {
for(int i = 0; i < [Link]; i++) {
int k = 1;
while(k < [Link]) {
[Link](arr[i]);
k *= 3;
}
}
}
Find time complexity and explain logarithm base impact.

Question 10:
void q10(int[] arr) {
if([Link] <= 1)
return;

int mid = [Link] / 2;


int[] left = new int[mid];
int[] right = new int[[Link] - mid];

q10(left);
q10(right);
}
Write recurrence relation and solve using Master Theorem.
Also find space complexity.

You might also like