CODEWITHSUNDEEP
javaperformancealgorithmbig-o
Vimzy
Vimzy

Reputation: 1965

Analyzing Nested Loop Running Times?

I was going through some practice problems and having a hard time understanding how to analyze the running times of these for the loop functions given below. Could someone please go through it step by step for me through the entire thing?

For each of the functions given below, I have to give the order of growth (as a function of N) of the running times of each of the following code fragments?

int sum = 0;
for(int n = N; n>0; n/=2) 
 for(int i =0; i <n; i++)
  sum++; 

int sum = 0;
for(int i = 1; i<N; i*=2) 
 for(int j =0; j <i; j++)
  sum++; 


 int sum = 0;
    for(int i = 1; i<N; i*=2) 
     for(int j =0; j < N; j++)
      sum++;

Upvotes: 1

Views: 1541

Answers (1)

chiwangc
chiwangc

Reputation: 3577

Case 1

int sum = 0;
for(int n = N; n>0; n/=2) 
 for(int i =0; i <n; i++)
  sum++;

When the value n for the outer loop is fixed, the work done of the inner loop is n. Since the outer loop takes values N, N/2, N/4, ..., N / 2^⌊log(N)⌋, the total work done is given by:

  N, N/2, N/4, ..., N / 2^⌊log(N)⌋
= N * (1 + 1/2 + 1/4 + ... 1 / 2^⌊log(N)⌋)
< 2N
= O(N)

Case 2

int sum = 0;
for(int i = 1; i<N; i*=2) 
 for(int j =0; j <i; j++)
  sum++;

When the value i for the outer loop is fixed, the work done of the inner loop is i. Since the outer loop takes values 1, 2, 4, ..., 2^(⌊log(N)⌋), the total work done is given by:

  1, 2, 4, ..., 2^(⌊log(N)⌋)
= 2^(⌊log(N)⌋+1) - 1
= 2 * 2^⌊log(N)⌋ - 1
< 2 * 2^log(N)
= O(N)

Case 3

 int sum = 0;
    for(int i = 1; i<N; i*=2) 
     for(int j =0; j < N; j++)
      sum++;

No matter what value the outer loop i takes, the work done of the inner loop is N. Since the outer loop takes values 1, 2, 4, ..., 2^(⌊log(N)⌋), the total work done is given by the number of possible values of the outer loop multiplies by N, hence the total work done is:

O(log(N)) * N = O(N log (N))

Upvotes: 2

Related Questions