time complexity question in C++

[Bluga]

#1. Given the following code, why is the time complexity O(n) ??


sum = 0;
for (k = 1; k<=n; k*=2)
for (j =1; j <=k; j++)
sum++;


#2. Given the following code, why is the time complexity O(n^2) ??

/* delta and x are float, not int */
x = n;
delta = 1/n;
while (x>0)
x = x-delta;

 

[RSI]

It just is. Just accept it!

 

[Bluga]

i need to know why

 

[gopunk]

sum = 0;
for (k = 1; k<=n; k*=2)
for (j =1; j <=k; j++)
sum++;


what does k*=2 do?

 

[RichieZ]

<< It just is. Just accept it! >>



Haha same here, order of operations escape me.



<< what does k*=2 do? >>


sets k to k*2

 

[StormRider]

<<
what does k*=2 do?
>>



It's shorthand for k = k * 2

 

[Bluga]

<< what does k*=2 do? >>



that line causes O(logn), but i'm not sure how it turns to O(n)?

 

[Bluga]

ttt

 

[gopunk]

well i can see why it would be O(n) for best case... can't see it for worst case though.

wait... so if you look at the values, you have

n | operations
1 | 1
2 | 3
3 | 3
4 | 7
5 | 7
6 | 7
7 | 7
8 | 15

and so on... which means that worst case is (n-1) + n... which is 2n - 1, which is O(n). at least that's how i see it...

 

[gopunk]

bump for my answer

 

[MGMorden]

Well, for #2 delta is the inverse of n and x (at first) is n.
So n - y (1/n) = 0.
So n - y/n = 0.
Y is the number of iterations until n = 0.
So we bring over the y/n and get n = y/n.
Multiply both sides by n and get y = n^2.
And hence n^2 iterations means O(n^2).

Working on #1 now . . .

 

[Bluga]

Thanks

 

[Bluga]

<< So n - y (1/n) = 0. >>



where did this came from?

 

[MGMorden]

<<

<< So n - y (1/n) = 0. >>



where did this came from? >>



n is our initial value. delta is 1-n and this doesn't change. now each time the loop executes delta is taken away from x (which was set to n initially). Therefore it will take y # of iterations before x (which is n) becomes 0. n - y(delta) = n - y (1-n) = 0.

 

[MGMorden]

Ok, for #1 . . . . Time complexity of two nested loops is time complexity of loop 1 * complexity of loop 2. k doubles each time (making it approach termination value of n very quickly) in the outer loop, giving a time complexity of O(log(n)). Now in the inner loop the loop must always iterate k times, which as stated before doubles each time, giving loop 2 a complexity of 2^n. so the entire set has a complexity of O(2^(log(n))). Since the log is base 2 (k doubles each time) and the exponent base is also two they cancel each other out and just leave O(n).

 

[MGMorden]

BTW, which class is this for? I had to do a LOT of time complexity problems in my data structures class. Just hope they don't make you write a B-Tree (not same thing as binary tree by a long shot). I got mine working but man did I pull my hair out on that one. Several of my friends took 0's on that assignment.

 

[bUnMaNGo]

It's probably for some algorithms analysis class... I had to take two of those... one last spring, and one last quarter... God help me if I had to write another inductive proof

 

[hans007]

<< #1. Given the following code, why is the time complexity O(n) ??


sum = 0;
for (k = 1; k<=n; k*=2)
for (j =1; j <=k; j++)
sum++;

say n is 32


then the k loop runs 5 times which is logn, for n = 1 , 2 , 4, 8 , 16, 32 , the second loop then runs the sum of all those N's so for n=64 then it runs the amount of times 1+2+4+8+16+32+64 = 127 . so basically its 2n-1.

that would be sooo the bottom loop runs the sum of all the N's in the k for loop. that is what 63. O(2n-1) for that reason i hafve no idea why the answer is O(n) but i suppose 2n-1 is a linear problem and not exponential so its O(n) . i think anyways.


#2. Given the following code, why is the time complexity O(n^2) ??

/* delta and x are float, not int */
x = n;
delta = 1/n;
while (x>0)
x = x-delta; >>



in this one x doesnt decrease as much relatively as n get larger. so its defniitely slower running and not linear like the ohter one. it grows a whole lot in time length as n is increased. from that alone you can cancel out o(logn) or o(n) as its growth functions.


it alwyas takes x/(1/n) times to finish the loop. that is x/(1/n) and since x=n that is n/(1/n) which is n^2.

 

[Bluga]

Thanks for the replies.

We have to implement Multiway Search Tree right now, is it the generalization of B-Tree? thanks alot.