I have an exam this coming week in Advanced Programming would appreciate a walk through for this question, is there any best way to approach it so any Big Oh question becomes easier?

1(b) [8 Marks]

For the typical algorithms that you use with pencil and paper, what is the time

and space complexity of the following in a Big-Oh sense?

(i) Adding two n-digit numbers [2 Marks]

(ii) Adding an n-digit number to an m-digit number [3 Marks]

(iii) Multiplying an n-digit number by an m-digit number [3 Marks]

1(c) [14 Marks]

(ii) What does the following code do? What is its time complexity in

a Big-Oh sense? [10 Marks]

int product = 1;

for ( int i = 1; i <= n; i ++ ) {

for ( int j = 1; j <= i; j ++ ) {

if ( j % i == 0 ) {

for ( int k = 0; k < j; k ++ ) {

product *= (i * j);

}

}

}

}

The purpose of Big-O notation (and analysis) is to answer the question: When n gets big, how do my resource requirements grow?

The resource here can be time, it could be space (memory), or something else entirely if you want. Usually, we talk about time and space.

Let me emphasize the focus on the growth of your resource requirements when n gets big, because this is why in this type of analysis, we freely ignore certain things, but not other things (which can be a source of confusion). When we are looking at big values of n, only the most significant growth terms become relevant. For example, if you are looking at n^2 + n, and n is something like a billion, the n^2 term far far outweighs any contribution from the n term. So Big-O notation does not make any distinction between n^2 + n, and n^2. Additionally, we are concerned with growth as n gets larger and larger, so things like constant factors also become irrelevant. We can always gain a factor of 2 speed-up in our program by using a computer that is twice as fast. If we are concerned about how much more time the algorithm might take between increasing values of n, then our analysis can ignore these constants. So Big-O notation does not make any distinction between, say, 2*n^2 and n^2.

These two guidelines are the basis of most of your "reduction" rules.