big o - What would be the tight asymptotic runtime (Big Theta) for these algorithms?

Question

Question 1

 public void guessWhat1(int N){
  for (int i=N; i>0, i=i/2){
  for (int j=0; j<i*2; j+=1){
  System.out.println(“Hello World”);
  }
 }
}

The first loop will run for log(n). The second loop will run for log(n).

The upper bound is O(log^2(n). What would be Big Θ?

Question 2

 public void guessWhat2(int N) {
 int i=1, s=1;
 while (s<=N) {
  i += 1;
  s = s + i;
 }
}

The upper bound for this is O(n). I am not quite sure about the Big Θ.

It would great if someone could clarify on these. Thank You

Answer 1

Lets get clear with the definitions of the notations first.

Big O: It denotes the upper bound of the algorithm.

Big Theta: It denotes the average bound of the algorithm.

For your first question

public void guessWhat1(int N){
  for (int i=N; i>0, i=i/2){
  for (int j=0; j<i*2; j+=1){
  System.out.println(“Hello World”);
  }
 }
}

For i=N, inner loop runs 2N times, i=N/2 inner loop runs for N times, for i=N/4 inner loop runs for N/2 times..... so the total complexity = O(2N+N+N/2+N/4+...+1) which is equal to O(N(2+1+1/2+1/4+....1/N))= O(N(3+1/2+1/4+....1/N))

N(3+1/2+1/4+....1/N) = N( 3 + 1 - (0.5)^logN ) = O(N(4-1/N)) = O(N) So the complexity is O(N), even in theta notation its the same N as the above loops takes the same time for all cases.

For your second question

public void guessWhat2(int N) {
 int i=1, s=1;
 while (s<=N) {
  i += 1;
  s = s + i;
 }
}

The while loop takes O(sqrt(N)). Same as above, here also the theta notation will also be the same as big O notation, which is sqrt(N).

The theta notation varies from big O if input has multiple cases. Lets take an example of insertion sort https://en.wikipedia.org/wiki/Insertion_sort where N is the size of the input array. If the input array is already sorted it takes linear time, but if the input array is reverse sorted it takes N^2 time to sort the array.

So in that case for insertion sort, the time complexity is O(N^2).

For best case it is theta(N) and for worst case its theta(N^2).