Extremely easy Time complexity Q

[Traveldixie]

Table t[1...n]
int s, i;

i=1;
s=0;
while(i<=n){
s = s + t;
i++;
};

Complexity : is it n+2 or 2n+2 ?
At the
the line s = s + t;
isn't the adding of t a simple constant assignment?
Or am I traversing the whole table still making it an extra &quot;n&quot;-factor?

Please help us out here coz we're disagreeing

Thank you!

 

[PerFnurt]

I'd guess its O as you have 1 linear iteration.

Is far as I recall (was 10 years since I took any CS class) you dont add constants in the complexity, ie there's no such thing as n+2.

But I could be mistaken. As I said, its been a while...

/Per

_{if (typos) cout << &quot;My fingers are faster than my brain. Sorry for the typos.&quot;;}

 

[Traveldixie]

yes you're right, no constants in the complexity; actually I was more wondering about the best/worst case scenarios, so the &quot;runtime-function&quot; ...
I understand it's an O-function allright
is t considered as a constant or not..? or is it traversing the whole table to check the index i...?
Thanks already for replying so fast!

 

[PerFnurt]

Again...using old and possibly erroneous memorybanks...the thing to consider in above would be the iteration comparison, ie

i<=n

In the above I dont see any best/worst case as one could with for example a sorting algoritm (ie worst case for quicksort is an already sorted collection).

But I have a feeling I might be missing the point here :-|


/Per

_{if (typos) cout << &quot;My fingers are faster than my brain. Sorry for the typos.&quot;;}

 

[Traveldixie]

nono your banks are still up-to-date
mine don't even have a date yet..heh..

it's indeed the i<=n factor..
and the best case is the same as the worst..
I'm just wondering for this comparison to be made, if it will have to &quot;walk&quot; from 1 all the way to n *first*, (hence make it from n to 2n...) or if it can &quot;see&quot; directly n, which in my opinion(again )would make the loop not necessary the second time (hence making it 'n'...)

 

[PerFnurt]

Its n (usual disclaimers applied)

I assume you mean t[n]
Accessing tables or arrays is O(1).
Ie retrieveal of t[23] or t[29346239842] is immediate.
(which is what one tries to accomplish by using for example hash tables)

If it infact had to walk all the way to n in every iteration wouln't it be
n²
rather than 2n?


Side note:
Actually I got in trouble with a similar thinge as I has had some similar problem where s was a string (and I new that string assignment results in some &quot;internal&quot; iteration) and went into a quite complicated complexity, when the answer was really just n, one simply ignored the inner workings of string assignment.



/Per

_{if (typos) cout << &quot;My fingers are faster than my brain. Sorry for the typos.&quot;;}

 

[Traveldixie]

First of all let me thank you for your time answering me
That's what I was looking for yea the immediate or not retrieval of t[n] (and yea I wrote that, but coz of TGML it wouldn't allow me...:\)

as for n² or 2n...I would hope (if I understand well that is.. ) that it's 2n then..wouldn't n² only be the case in a nested iteration..? (which I thought is not at hand here..(?))

As for your side note, thank you for enlightning me on that ..has it to do with inner traversing a string char by char. perhaps?

Thanks again!

 

[PerFnurt]

>First of all let me thank you for your time answering me

Hey, no problem. Its kinda fun trying to recall stuff youve spent years on trying to forget

So, we came to the conclusion you where right, retrieval is immediate and all that.
----
Leaving that subject and assuming that t[n] retrieval did infact require a 1..n iteration:
(1) while(i<=n) is O.
(2) t[n] retrieval is O.
(3) The whole tingie is O(n²) since for every (1) you'd do a (2).

Ie wouldn't it infact be a nested iteration?

>has it to do with inner traversing a string char by char. perhaps?

Well I thought like &quot;if I copy n bytes from here to there that'd mean some kind of traversal&quot; (as it infact does), but that had nothing to do with the &quot;outer&quot; algorithm's complexity, which the original problem was about. I just shot my self in the foot (I didnt fail the exam as I recall it, I did get some points for effort





/Per

_{if (typos) cout << &quot;My fingers are faster than my brain. Sorry for the typos.&quot;;}

 

[Traveldixie]

yes of course and this is where we find eachother back on the same track taking different ways at the beginning
I'm good at confusing myself and others, so it's nice to have someone to help me out at times

I understand it now again and so since it's immediate it's 2n..

I guess I lost the bet

PC's will always have more mysteries for me than life itself, heheh

Take care

 

[PerFnurt]

>I understand it now again and so since it's immediate it's 2n

Oh. I thought that since its immediate its n.

Oh well...

/Per

_{if (typos) cout << &quot;My fingers are faster than my brain. Sorry for the typos.&quot;;}

 

[Traveldixie]

heheh..yea n for time complexity, 2n for runtime-function is what I meant but it's the complexity that counts...as for the function, I think there's a spelling mistake in this course I have..should be n + 2 , making the complexity, like you said, n..

 

[PerFnurt]

>I'm good at confusing myself and others

I see what you mean


/Per

_{if (typos) cout << &quot;My fingers are faster than my brain. Sorry for the typos.&quot;;}