Big-Oh (best and worst case)

[raphnguyen]

Hi all, I am an absolute beginner to data structures and algorithms. The book that our class is using isn't all that helpful or perhaps I am not digesting the information that well. It is early in the semester and I am already struggling, so I am really hoping that someone is able to help me understand these topics better.

An exercise asks us to give the big-Oh characterization, in terms of n, of the worst-case running time of Algorithm 1 (below) and the best-case running time.

Algorithm 1
Let A be a given array of n integers

for i<-0 to n-1 do
     if (A[i] = 0) then
          for j<-0 to i do
               A[i] <- A[i] + A[j]

Like I said, I am completely new to this topic and am having a difficult time understanding the material. The best I have managed to do is just to turn the algorithm into code like so:

for (i = 0; i<n; i++) {
     if (A[i] = 0) {
          for (j = 0; j<i+1; j++) {
               A[i] = A[i] + A[j];
          }
     }
}

Would love it if someone could explain how to go about solving this problem in detail so that I can apply the same knowledge to some of the other exercises. Thanks in advance.

[Ledidas]

Worst =O(n^2)
Best = O(n)

[raphnguyen]

Thanks. I was actually able to figure this out after browsing some online text. Another exercise is:

[code]for (int i=0; i<n; i++) {
for (int j=0; j<i*i; j++) {
sum += data[i] * data[j];
}
for (int j=0; j<4*n; j++) {
sum += data[i] + data[j];
}
}[code]

For this problem, the best and worst case scenario would be O(n^3) right? n(n^2 + 4*n) = n^3 + 4*n^2 and we take the highest factor?

How can I count the basic operations performed on the algorithm? How can I compute the total number of basic operations, and based on this number provide a Big-Oh estimate of the running time?