Simple Algorithm

[filipgothic]

I need help with this two questions, its not hard for experts I guess, here it is:

Determine the time of executing the following algorithm fragment:

a)

if (x == 0) then
      for i = 1 to n do
           a[i] = i;

b)

 i = 1;
 repeat
            a[i] = b[i] + c[i];
            i = i +1;
            until (i == n);

Thanks in advance

[phorce]

What have you done to understand the problem? Do you expect someone to do your problem? If it's "simple" and "not hard" then surly you would be able to do this yourself?

[DavidB]

What kind of answer are you looking for? An exact time in milliseconds? I don't think anybody could give that kind of answer. It would depend upon the hardware you use and several other factors.

Are you supposed to write a program execution timer? You'd have to get a hook into the clock cycles of your computer and take the time before and after the code block executes.

Or are you just looking for the order of the algorithm? For example, order 0.618*n, n, n log(n), log(n) log(n), etc.?

[Ancient Dragon]

You'd have to get a hook into the clock cycles of your computer

That would be going a bit to the extreme -- just using standard C function clock() and repeating the algorithm a million times would probably be sufficient.

clock_t t1,t2;

t1 = clock(); // get starting time
for(int i = 0; i < 1000000; i++)
{
    // do algorithm here
}
t2 = clock(); // get ending time

int diff = t2-t1;

[filipgothic]

phorce I said is simple for expert if u can read pls, and guys time is not defined so I guess is easier to go with seconds, I know is simple because no one put so much effort in this, neither professor or other students, we did not even studied this, it was just like homework, bonus if you understand, but we must do it anyway. Its buble sort algorithm

[Ancient Dragon]

clock() returns milliseconds, time() returns seconds. If it's bubble sort then just to the bubble sort once instead of a million times as in my previous post. But you will have to give it a pretty large array so that the time is measurable. If the entire time to do the bubble sort is less than 1 millisecond then the measurable time will be 0.

[NathanOliver]

I would think they are just looking for big O notation since they give no size for n.

[filipgothic]

well am not sure, but there is no real explanation for this question, just to get time interval for algotihm, without any extra code, just from existing one, idk if that is possible

[filipgothic]

I have example

for i = 1 to n do
   for j = 1 to n do
       if (i < j) then
           swap(a[i,j], a[j,i]);



       and answer is

       T(n)=n*n*(1+1)=2n²

[filipgothic]

bump

[filipgothic]

anyone, this is from second year of IT, anyone passed that? I can't figure out formula for answering, every example is different, can anyone help?

[Ancient Dragon]

What have you studied about big O notation? Here are some examples

[filipgothic]

aha, I see is similiar but not same, I don't know how to count 1+1+1+2 blbla based on what, how can I know what lines takes 1,2,3 seconds or when should I use + or * I can't know anything from example I gave above, and only those I have in book

[Ancient Dragon]

Didn't you read any of the links I gave you? The very first one explains how to do it.

[filipgothic]

am trying to understand it, loop thing, how can I determine how much I have it in my example

[Ancient Dragon]

if (x == 0) then  // O(1) simple variable access
      for i = 1 to n do // O(n)
           a[i] = i; // O(1) simple variable access

Now, read this again until you understand it

[filipgothic]

T(n)=1*n+1=2n

is this correct?

[mike_2000_17]

anyone, this is from second year of IT, anyone passed that?

Seriously? What did you do the first year? Make macaroni art?

From the example:

if (x == 0) then  // O(1) simple variable access
      for i = 1 to n do // O(n)
           a[i] = i; // O(1) simple variable access

You just multiply every nested thing, so, you get:

T(n) = O(1) * O(n) * O(1) = O(n)

That's it. Any constant factor disappears because they are unknown anyways, so, answers like O(2*n) are impossible, it would just be O(n). And any terms that are smaller than the dominant term also disappears from the final answer (although sometimes keeped as intermediary result to show sub-complexities). For example, if you have this:

for i = 1 to n do  // O(n)
    a[i] = i;  // O(1)
    for j = 1 to n do  // O(n)
        b[j] += a[i];  // O(1)

Then, you get this:

T(n) = O(n) * (O(1) + O(n) * O(1))
     = O(n + n^2)
     = O(n^2)

because a quadratic term (O(n^2)) grows much bigger than a linear term (O(n)), and thus, "swallows" it when n is large.

Overall, this kind of stuff is very simple. For every loop, you just figure out how many times (on average) the loop will have to execute (e.g., in terms of the number of elements in an array, or some other quantity like that). And, for whatever is just a simple statement, you just count it as a O(1) operation. Then, nesting equals multiplication (e.g., you multiply the number of times a loop executes with the complexity of whatever is executed at each iteration), and otherwise, you just add them. You perform all the multiplications and additions, you re-group the terms in terms of constant / linear / quadratic / etc.., you remove the factors in front of them (because they don't matter), and you keep only the biggest term (highest order).

guys time is not defined so I guess is easier to go with seconds

No, as you said, time is not defined, so, you can't count it in seconds, or any other unit. It is meaningless to talk about actual execution time when you are given an abstract (pseudo-code) example, with no real data, no real compiler and no real machine to run it on. Clearly, the question asks for an abstract time, i.e., just an order estimate, as in, a Big-O estimate. Some computer scientist (that write examples like these) are so disconnected from reality that they often forget to mention that they only want abstract answers and only ask abstract questions. So, it's safer to just assume everything to be abstract all the time unless stated otherwise.

[filipgothic]

hm we did microsoft office in first year and stuff like that, cad, cam etc so dont be rude to me...

[filipgothic]

here is my example

or i = 1 to n do
for j = 1 to n do
if (i < j) then
swap(a[i,j], a[j,i]);

and answer is
T(n)=nn(1+1)=2n²

so first and second lines are n and third and fourth are 1+1 not * and answer is 2n²

so for this one its like this

i = 1 / / Simple variable (1)
  repeat


                 a [i] = b [i] + c [i] / / Simple variable (1)


             i = i +1; / / Simple variable (1)
             until (i == n) / / (n)

The solution:
T (n) = 1 * 1 * 1 *n = n

I asume

[filipgothic]

can anyone confirm my answer, because today is last day to send in answers

[NathanOliver]

Yes what you came up with is correct. If you want to write it in big-O notation it would be O(n).

[filipgothic]

a)

if (x == 0) then     //Jednostavna promenjljiva (1)
      for i = 1 to n do //(n)
           a[i] = i; //jednostavna promenljiva (1)

Resenje:
T(n)=1*n*1=n

b)

 i = 1; //Jednostavna promenjljiva (1)
 repeat
            a[i] = b[i] + c[i]; //Jednostavna promenjljiva (1)
            i = i +1;  //Jednostavna promenjljiva (1)
            until (i == n); //(n)

Resenje:
T(n)=1*1*1*n=n

here is final results

thanks for helping guys

[NathanOliver]

A should actually look like this

if (x == 0) then     //constant (1)
  for i = 1 to n do // linear(n)
       a[i] = i; //constant (1)

Resenje:
T(n) = O(1) + O(n) * O(1) = O(n)

B should look like this

i = 1; //constant (1)
repeat
    a[i] = b[i] + c[i]; //constant (1)
    i = i +1;  //constant (1)
until (i == n); // linear(n)

T(n) = O(1) + O(1) * O(n) = O(n)

[filipgothic]

I have corections, can anyone check this

a)

if (x == 0) then     //Jednostavna promenjljiva (1)
      for i = 1 to n do //(n)
           a[i] = i; //jednostavna promenljiva (1)

Resenje:
T(n)=1 + n*1=n 

b)

 i = 1; //Jednostavna promenjljiva (1)
 repeat
            a[i] = b[i] + c[i]; //Jednostavna promenjljiva (1)
            i = i +1;  //Jednostavna promenjljiva (1)
            until (i == n); //(n)

Resenje:
T(n)=1 + (1 + 1 ) *n= 2*n

[filipgothic]

what about b

u missed one 1?

[mike_2000_17]

They are both correct, although people would generally write them as O(n) in both cases, because the 2 in the answer to (b) is not meaningful.

[filipgothic]

alright I will mark this as solved, thanks everyone who helped