Scribd
Upload
3 views3 pages

Running Time and Algorithm Complexity Analysis

The document analyzes the running time and complexity of various algorithms, comparing Program A (150N log N) and Program B (N²) based on their performance for different values of N. It discusses the complexities of combined algorithms, modified insertion sort, and provides Big-O analysis for several code fragments. Key takeaways include that Program A is better for large N, while Program B may perform better for small N, and the overall complexities of different operations are outlined.

Uploaded by

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

Running Time and Algorithm Complexity Analysis

The document analyzes the running time and complexity of various algorithms, comparing Program A (150N log N) and Program B (N²) based on their performance for different values of N. It discusses the complexities of combined algorithms, modified insertion sort, and provides Big-O analysis for several code fragments. Key takeaways include that Program A is better for large N, while Program B may perform better for small N, and the overall complexities of different operations are outlined.

Uploaded by

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

fi

Q1. Analysis of Running Time


(a)
Program A (150N log N) is better for large values of N
because N² grows much faster than N log N. For very big N
like 10,000, the difference is signi cant.
(b)
Program B (N²) might be better for small values of N (like
below 100) because 150N log N might be bigger than N²
when N is small.
(c)
No, Program B can’t always be faster than Program A. For
small N it might be, but for large N, the quadratic term
makes it worse.
————————
Q2. Complexity of Combined Algorithms
(a)
Two O(N) operations run one after another, so the total is
still O(N).
fi
(b)
O(N²) + O(N) Since N² grows faster, the total complexity
fi
is O(N²).
fi
(c)
O(N) for the rst algorithm.
O(N log N) for the N binary searches.
O(N) for the nal algorithm.
The biggest term is O(N log N), so that’s the nal answer.
Q3. Modi ed Insertion Sort

void insertionSort(int[] arr) {


int copies = 0;
int comparisons = 0;

for (int i = 1; i < [Link]; i++) {


int key = arr[i];
int j = i - 1;
copies++;

while (j >= 0) {
comparisons++;
if (arr[j] > key) {
arr[j + 1] = arr[j];
copies++;
j--;
} else {
break;
}
}
arr[j + 1] = key;
copies++;
}

[Link]("Total Comparisons: " + comparisons);


fi
[Link]("Total Copies: " + copies);
}

• When sorting an inversely sorted array, the number of comparisons


and copies was very high, con rming O(N²) complexity.
• When sorting an almost sorted array (just a few elements out of
place), it needed way fewer comparisons, making it closer to O(N).
Q4. Big-O Analysis of Code Fragments

1- O(N) (Simple loop, runs N times)

2-O(N) (Runs about N/2 times, but Big-O ignores


constants)

3-O(N²) (Nested loop runs N × N times)

4-O(N) (Two separate loops O(N) + O(N) = O(N))

5-O(N³) (First loop is O(N), second is O(N²), so total is


O(N³))

6-O(N²) (Runs like a triangular number sum: 1 + 2 + 3 +


… + (N-1) ≈ N²/2)

7-O(N⁵) (First loop is O(N), second is O(N²), third is


O(N²) in the worst case O(N × N² × N²) = O(N⁵))

8-O(log N) (i doubles each time, so the loop runs log₂(N)


times)

You might also like