Homework help! Big-O notation...

[DonnieT2]

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!

[deceptikon]

It all looks good to me. To answer G, your answer for D will help. Just remember that it's a nested loop and the solution will be apparent. :)

[DonnieT2]

It all looks good to me. To answer G, your answer for D will help. Just remember that it's a nested loop and the solution will be apparent. :)

Thank you very much for the input. What I've come up with for the last one is n * log n which would be a Big O notation of O(n(log n)). Is my analysis correct or did I flub it up? Thanks again!

D. O(log n)
For any n value the For loop will have log n iterations meaning the Big O notation is O(log n).

E. O(n^2)
For any n value the For loop will have n^2 + n iterations meaning the Big O notation is O(n^2).

G. O(n(log n))

[deceptikon]

What I've come up with for the last one is n * log n which would be a Big O notation of O(n(log n)).

That's what I was thinking of.

[mrnutty]

Also for B), O(n+m) \in O(n) so you can just say O(n)

[DonnieT2]

Thanks everyone! I really appreciate the help and input.