In Big-Θ notation, analyze the running time of the following pieces of code/pseudo-code. Describe the running time as a function of the input size (here, n). You should always explain your work when solving mathematics problems.
I need help figuring out how to find runtime analysis. When put into pieces of code, I am having trouble reaching my answer. Here are some example problems I am stuck on.
Problem 1:
1 2 3 4 5 6 7 8 9 10 11 12
for (int i = 0; i < n; i ++)
{ // A is an array of integers of sufficient size
if (A[i] == 0) {
for (int j = 0; j <= i; j++) {
if (A[i] == 0) {
for (int k = 0; k <= j; k++) {
A[i] = 1; // this is no typo
}
}
}
}
}
Problem 2:
1 2 3 4 5 6 7 8 9
for (int i = 1; i < n; i *= 2)
{
func(i);
}
void func(int x) {
if (x <= 1) return;
func(x-1);
}
Problem 3:
// This problem uses the same singly linked list Node structure you've seen a lot
// A is an array of integers of sufficiently large size
Simply, Θ looks for a very tight upper and lower bound. You are going to have a hard time of that with problem 1 (what if A[] is all zeros? what if A[] is all non-zero? The difference is an order of magnitude. You are better off calculating Big-O and Big-Ω separately.)
Problem 2 you can compute Big-Θ. Remember that inner loops that do less and less of N each time is a logarithmic complexity.
Etc.
Remember: Big-O is upper bound (worst case scenario), Big-Ω is lower bound (best case scenario) and Big-Θ exists only if Big-O equals Big-Ω.