Asymptotic Analysis:

I'm not sure how many of you here have a Computer Science or Computer Engineering background, but I just thought I would do a quick refresher with some problems I worked on years back when I was 18 - 22. Today, I'm quite the old geezer (just kidding I'm not that old, I'm in the 28 - 34 year old range), but compared to some of you I am quite ancient/prehistoric (JK I hope that some of you 18 - 24 year olds don't think that). In any case, enough kidding around. How many of you remember from your days as a Comp sci/eng student Asymptotic analysis? Being able to measure the efficiency of a programme or an algorithm using Big-O (tightest bound) notation? I wanted to quiz you guys on it with a few problems? WARNING: THIS IS NOT A TUTORIAL, it's a refresher for some Computer Science/Computer Engineering majors who may have gotten rusty. The code is in java, so you might want to be a little familiar with java.

Problem 1.

Can you guys give me in terms of Big-O notation the tightest bounds for the code below:

int someRandomArray( int[] array1) {

   int sum = 0;
   for (int i=0; i<array1.length;  i++) {
      for (int j=1; j<array1.length; j*=2) {
         if (array1[i] > array1[j])
            sum += array1[i];
      }
   }
   return sum;
}
}

Problem 2:

Calculate tightest bounds in terms of Big-O

int sumSome(int[] arr){
   int sum = 0;
   for (int i=0; i<arr.length;  i++) {
      for (int j=0; j<arr.length; j+=2) {
         if (arr[i] > arr[j])
            sum += arr[i];
      }
   }
   return sum;
}

Problem 3:

True or false: two algorithms run at O(n) time or linear time, thus, these two algorithms will always run at the same speed regardless of the amount of data we must process.

Have fun ladies and gents

No one likes this thread?

Fulaman198:
No one likes this thread?

A layman following silently. May Allah reward you abundantly in this world and next.

algorithms, that scary thing.
i will just do a rough guess coz i am not a cs student. 1. 0(n²)
2. Same as 1.
3. true.
*exits thread via back door *

Both 1 and 2 run at quadratic time O(n^2) 3 is false.

Amoto94:

A layman following silently. May Allah reward you abundantly in this world and next.

Amiin, Very kind words brother, thank you very much. May Allah reward you abundantly in this world and the next as well and may you continue to be an amazing fountain of wisdom. Thank you very much for your support.

@Babatope88 and Crotonite be careful about #1, O(n^2) is indeed an upper bound for the algorithm if we are assessing it using Big-thetha. But it is asking for tightest bound. Since the inner loop is increasing exponentially, its tightest bounds is O(log n). Thus, for the entire equation, if we run asymptotic analysis, it's running at O(n log n) time. You are both correct about #2, number 3 is false, so good work.

Why should they reply? If it's to discuss PHP, Lavarel (latrine, whatever), they will be throwing their noses everywhere. Bunch of copy and paste typists! Anyway I don't know the answer to your quiz. I tend to shy away from the art of theoritical computing - but I know I love it, somewhere.

came that late, pls post another!

Honestly, I still do not feel as though I truly understand Big O notation, but I knew that the first one could not have been O(n^2). The exponential increase of the second loop would require a log n. I know this, though I do not fully understand it.

Anyhow, with the nature of processing nowadays, algorithmic speed is not something most programmers concern themselves with (though I am not saying that they should ignore it), especially those who program with scripting languages. Users of compiled languages on the other hand seem to be more concerned with algorithmic speed than their scripting counterparts.

I still try to read up on Big O notation from time to time, waiting for the moment when it will all finally click and make sense to me.

Let us kwontinue. I love algorithms!

ChinenyeN:
Honestly, I still do not feel as though I truly understand Big O notation, but I knew that the first one could not have been O(n^2). The exponential increase of the second loop would require a log n. I know this, though I do not fully understand it.

Anyhow, with the nature of processing nowadays, algorithmic speed is not something most programmers concern themselves with (though I am not saying that they should ignore it), especially those who program with scripting languages. Users of compiled languages on the other hand seem to be more concerned with algorithmic speed than their scripting counterparts.

I still try to read up on Big O notation from time to time, waiting for the moment when it will all finally click and make sense to me.

You will definitely get the hang of it, Keep at it and it will click sooner or later. Best of luck brother

But Fulaman198, I suspect that the second loop in program 1 will be an infinite loop. J is initialized to 0, so all future attempts to multiply j by 2 will still give you 0. I think you should use 1-based counting instead.

enigmatique:
But Fulaman198, I suspect that the second loop in program 1 will be an infinite loop. J is initialized to 0, so all future attempts to multiply j by 2 will still give you 0. I think you should use 1-based counting instead.

You are right, I'm sorry, that was a typo

Fulaman198:

You are right, I'm sorry, that was a typo

Nah, no problem bro. Glad to be of help.

KazukiIto:
Why should they reply? If it's to discuss PHP, Lavarel (latrine, whatever), they will be throwing their noses everywhere. Bunch of copy and paste typists! Anyway I don't know the answer to your quiz. I tend to shy away from the art of theoritical computing - but I know I love it, somewhere.

take it easy on people, you dont learn things like this except you have to(degree requirement like the op) or are a sadist or extremely motivated.

And for those who did learn it outside school, they'd have forgotten all of it due to dis-use. Not much use of it in day to day programming tasks. Bringing us round circle to the head-scratching point of ignorance like those who never seen that sh*t b4.

op, does tightest bound mean the shortest runtime?
what does asymptotic mean by the way?
this kind unwashed grammer scares noobs off.

Wont 1 run in longer than log n time?
i.e n*log n even for its tighest bounds.

Fulaman198, pls are you a programmer? If yes, how proficient are you?

Fulaman198:
@Babatope88 and Crotonite be careful about #1, O(n^2) is indeed an upper bound for the algorithm if we are assessing it using Big-thetha. But it is asking for tightest bound.

I'm a bit rusty on algorithm analysis but isn't Big-thetha the same thing as tightest bound.

I stand to be corrected.