Hello all! I'm currently enrolled in an Algorithms course at my local university and have a question over an assignment. Here is the assignment:

Assignment 1

1. Give a big-Oh notation, in terms of n and m, of the running time of the following

procedures, including your explanations:

a. Procedure1(n)

```
for (i = 0; i < n; i++) {
for (j = n; j > i; j--) {
A[i][j] = j*A[i] + i*B[i];
}
}
```

b. Procedure2(n, m)

```
for (i = 0; i < n; i++) {
A[i] = A[i] - B[i];
}
for (i = 0; i < m; i++) {
A[i] = A[i] + B[i];
}
```

c. Procedure3(n)

```
for (i = 0; i < n; i++) {
for (j = n; j > 0; j--) {
A[i][j] = j*A[i] + i*B[i];
}
}
for (i = 0; i < n; i++) {
A[i] = A[i] + B[i];
}
```

d. Procedure4(n)

```
for i = 1 to log n do
A[i] = A[i] + i
```

e. Procedure5(n)

```
for i = 0 to n^2 + n do
A[i] = A[i] + i;
```

f. Procedure6(n)

```
i = 0;
while (i < 3*n^3 + 200*n^2 + 300*n + 10000) {
System.out.print(“Algorithm is fun!”);
System.out.print(" ");
i = i + 1;
}
```

g. Procedure7(n)

```
for (i = 1; i <= n; i++)
for (j = log(i); j > 0; j--)
printf("Most difficult one among this assignment!");
```

Here are the answers I've come up with. I'm here to learn so if I've screwed up on any part please correct me. Thanks in advance for your help!

A. O(n^2)

The first For loop will run n iterations and the second For loop will run n iterations as well. Therefore for every outer iteration, the inner loop is doing n iterations. For n outer iterations, each one of them the inner loop is doing n iterations so we have n^2 iterations for a given n making the Big O notation O(n^2).

B. O(n + m)

The first For loop will run n times and the second For loop will run m times. Since there is no nested loop the Big O notation is O(n + m).

C. n^2 + n = O(n^2)

The first For loop will run n iterations and the second For loop will run n iterations as well. Therefore for every outer iteration, the inner loop is doing n iterations. For n outer iterations, each one of them the inner loop is doing n iterations so we have n^2 iterations for a given n. The third For loop is not nested and will run n times making the total time complexity n^2 + n. The term n^2 is the fastest growing one meaning the Big O notation is O(n^2).

D. ? O(log n)

(I'm a little confused by the syntax and this is just an educated guess however I'm not sure how to explain it)

E. ? O(n^2)

(Same as above)

F. O(n^3)

The While loop will run 3n^3 + 200n^2 + 300n + 10000 iterations. The term 3n^3 is the

fastest growing one meaning the Big O notation is O(n^3).

G. ?

(Stumped)

Thanks again!