Runtime Analysis

[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:

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:

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

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:

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);
}

[Duthomhas]

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)

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

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

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!