### Runtime Analysis

closed account (G3AqfSEw)
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:
 ``123456789101112`` ``````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:
 ``123456789`` ``````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
 ``12345678910111213141516171819202122`` ``````Node *head = new Node; Node *curr = head; head->data = 0; head->next = nullptr; for (int i = 1; i < n; i++) { curr->next = new Node; curr = curr->next; curr->data = i; curr->next = nullptr; } for (int i = 1; i <= n; i++) { curr = head; while (curr != nullptr) { if (curr->data % i == 0) { for (int j = 0; j < n; j++) { A[j] ++; } } curr = curr->next; } }``````

Problem 4:
 ``123456789101112131415`` ``````double *a = new double [3]; int size = 3; for (int i = 0; i < n; i ++) { if (i == size) { int newsize = 3 * size; double *b = new double [newsize]; for (int j = 0; j < size; j++) b[j] = a[j]; delete [] a; a = b; size = newsize; } a[i] = sqrt(i); }``````
Last edited on
Runtime analysis is all about counting the number of times you repeat something. If you do it just once, you don't care.

`int n = 12;` Don't care.

`for (int n = 0; n < N; n++)` N times → O(N)

 ``12`` `````` for (int n = 0; n < N; n++) for (int m = 0; m < M; m++)``````

N * M times → O(M*N) → O(N2)

I do not presume you know the difference between O and Θ. Read here for more:
http://www.cplusplus.com/forum/beginner/169934/#msg848773

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-Ω.

Good luck!
Last edited on
Topic archived. No new replies allowed.