Question

I am currently taking an Analysis of algorithms class and can't find enough help for finding time complexities of algorithms and i have spent hours on my own trying to figure out the solution. Our book has good problems but no solutions or supplement is provided. And we don't have TA sessions or office hours. And, the professor's time is limited. And, there is also not that many help online for this topic (like examples). So, can someone help me to find time complexity functions of algorithms (that i will post). And, yeah I will mention if it's from the book or hw or both.

Answer 1

But, our homework is not graded anyways.

Answer 2

This ones from the book.
------------------------------------------

j=1;
while(j<=n/2)
{
i=1;
while(i<=j)
{
cout<<j<<i;
i++;
}
j++;
}

Answer 3

I know that the outer loop runs n/2 times but the inner loop depends on the outer loop - the value of j. So, I can't determine an exact function that for this algorithm.
And, I am sure this algorithm is close to Big O(n^2).

Answer 4

@jagatuba How are you on analysis of algorithms? Did your BSIT cover it?

Answer 5

I was supposed to have a concentration in SE, but my academic advisor dropped the ball on adding my concentration and I didn't even realize it until it was too late. Really ticked me off. In any case, while I should have had classes in analysis, the BSIT didn't cover that. However, I did do quite a bit of programming years ago, so am not half bad at looking at code and deciphering what it does.

So @myname, as long as you can convert into Big O, I can tell you how many times each line runs. From your OP it looks like you were having a bit of trouble determining how many times your inner loop runs. This is a simple matter of determining the sum of the numbers from 1 to N (N being the number of times the outer loop runs or n/2).

So, the formula for calculating the numbers 1 - N is N(N+1)/2. Since we know that N=n/2, we simply sub that in so we get

(n/2)((n/2)+1)/2

meaning each line in the inner loop runs (n/2)((n/2)+1)/2 times. Knowing this we can determine the number of times each line executes.

j=1; {1 time}
while(j<=n/2) {n/2 times}
{
i=1; {n/2 times}
while(i<=j) {(n/2)((n/2)+1)/2 times}
{
cout<<j<<i; {(n/2)((n/2)+1)/2 times}
i++; {(n/2)((n/2)+1)/2 times}
}
j++; {n/2 times}
}

Not sure if that helps at all, but it's the best I got.

Answer 6

Okay. Just gave myself a crash course in algorithm analysis, and you are right. This algorithm is quadratic, so every time the value of n is doubled the running time of the program increases n*n. So it would be:
\[O(n ^{2})\]

Answer 7

Just so we are clear, I'm not 100% on that answer. My second choice would be
O(n log n)
since on further reflection the outer loop seems to be logarithmic and the inner is linear. I'm a little more comfortable with this answer, but still not 100%. I'll have to study up some more. Any feedback or insights that you can provide back would be helpful.

Answer 8

Thanks a lot, I got it the time complexity is T(n)= ((n/2)((n/2)+1))/2 -- the one that you initially gave. It makes total sense now.
Yeah, and we are just counting the basic print operation in this case.