How to calculate Time Complexity for a given algorithm

Question

i, j, N, sum is all integer type. N is input.

( Code1 )

i = N;

while(i > 1)
{
    i = i / 2;
    for (j = 0; j < 1000000; j++)
    {
       sum = sum + j;
    }
}

( Code2 )

sum = 0;
d = 1;
d = d << (N-1);
for (i = 0; i < d; i++)
{
    for (j = 0; j < 1000000; j++)
    {
        sum = sum + i;
    }
}

How to calculate step count and time complexity for a Code1, Code2?

SO isn't a homework forum, use your text, or previously posted questions — SGM1
– SGM1, Commented Sep 11, 2013 at 14:21
@SGM1 Sorry. but it isn't homework. I study algorithm. it's self study. — iSangyoon
– iSangyoon, Commented Sep 12, 2013 at 15:00
@SGM1 In addition it's not homework question. I just think about. — iSangyoon
– iSangyoon, Commented Sep 12, 2013 at 15:01

No Idea For Name · Accepted Answer · 2013-09-11 14:14:47Z

1

to calculate the time complexity try to understand what takes how much time, and by what n are you calculating.

if we say the addition ("+") takes O(1) steps then we can check how many time it is done in means of N.

the first code is dividing i in 2 each step, meaning it is doing log(N) steps. so the time complexity is

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

the second code is going form 0 to 2 in the power of n-1 so the complexity is:

 O(s^(N-1) * 1000000)=  O(2^(N-1))

but this is just a theory, because d has a max of 2^32/2^64 or other number, so it might not be O(2^(N-1)) in practice

answered Sep 11, 2013 at 14:14

No Idea For Name

11.6k11 gold badges49 silver badges73 bronze badges

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

4 Comments

I have one question. d = d << (N-1); code's step is 2 ^ (n-1)?

depend on the d. if d=1 then yes, if d=2 then it's 2^n and so on

I Understand that now. :)

@iSangyoon glad to be of service