Analyzing Nested Loop Running Times?

Question

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++;

@ chiwangc, please refer to stackoverflow.com/questions/40952377/loop-runtime-issue — user7123229
– user7123229, Commented Dec 3, 2016 at 21:05

chiwangc · Accepted Answer · 2014-10-06 04:23:18Z

2

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

edited Oct 6, 2014 at 4:23

answered Oct 6, 2014 at 4:17

chiwangc

3,58716 gold badges28 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Vimzy Over a year ago

Thanks man, @chiwangc do you have any tips on approaching these problems bro? they always are a huge pain for me

chiwangc Over a year ago

@Vimzy I would suggest you first consider the work done of the inner loop condition on the outer loop being fixed. You can then find the total work done by summing over all possible values the outer loop can take (just like my solution). Also, I find writing out the first few indices of the loops really helps to give a more concrete picture of what's going on.

Vimzy Over a year ago

@chiwango where did you get "N / 2^⌊log(N)⌋" from in the equation? That's what's confusing me

Vimzy Over a year ago

and same thing for "1 / 2^⌊log(N)⌋" where are you getting these from?

chiwangc Over a year ago

Don't be too confused by this notation, I was just trying to be precise in the solution. 2^⌊log(N)⌋ simply means the largest integer that is less than N and is a power of 2 here. In the outer loop, you divide n by 2 until it becomes less than 1, and 2^⌊log(N)⌋ is the maximum number of times you can divide N by 2.

|

Collectives™ on Stack Overflow

Analyzing Nested Loop Running Times?

1 Answer 1

Case 1

Case 2

Case 3

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Case 1

Case 2

Case 3

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related