Please DONOT attempt this Big O question if you don\'t know the exact answer. Al
ID: 3675339 • Letter: P
Question
Please DONOT attempt this Big O question if you don't know the exact answer.
Algorithms question (Big O): Please explain me in details the order of growth (as a function of N) of the running times of each of the following code fragments:
a) int sum = 0;
for (int n = N; n > 0; n /= 2)
for(int i = 0; i < n; i++)
sum++;
b) int sum = 0;
for (int i = 1 i < N; i *= 2)
for (int j = 0; j < i; j++)
sum++;
c) int sum = 0;
for (int i = 1 i < N; i *= 2)
for (int j = 0; j < N; j++)
sum++;
Note: No copy/paste from Google search please. Send me the answer only if you have very clear concept on this
Explanation / Answer
/*
Basic Assumptions :
Each executable line will cost O(1).
*/
int sum = 0;
for (int n = N; n > 0; n /= 2)
for(int i = 0; i < n; i++)
sum++;
/*
For above code.
first line will cost O(1)
second line loop will run lgN times because we are decreasing the size of input by 2 after each iteration hence O(lgN)
third loop depends on the value of n obtained from first loop.
N+N/2+N/4+N/8.....1 = 2N-1 hence complexity of this loop will be O(2N-1).
Using asymptotic analysis which says when the value of N is very large constants can be ignore
which results in complexity of O(N)
hence the total complexity is O(N*lgN)
*/
int sum = 0;
for (int i = 1 i < N; i *= 2)
for (int j = 0; j < i; j++)
sum++;
/*
Same reasoning as above example.
*/
int sum = 0;
for (int i = 1 i < N; i *= 2)
for (int j = 0; j < N; j++)
sum++;
/*
first line will cost O(1)
second line loop will run lgN times because we are increasing the size of input by multiplying last input by 2. hence O(lgN)
third loop will run O(N) times
hence the total complexity is O(N*lgN)
*/