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);
}
}
}
}

As this problem is academic in nature, you should show us your attempted solutions, and we can comment on them.

0

Indie101Author Commented:

Ok no problem these are practice problems from last years test , its not like i want someone to do my homework,but I appreciate where you're coming from

This is my understanding for first problem, i went through this with tutor was really looking for another way of fully realising it

n+n = O(n )
n+m = O(n )
n*m = O(n^2)

For 2nd problem i put n through a serious of values from 1 through 4,

The first two loops are actions that introduce new variables. The third loop is a logical check and adds no variable

When putting values for n from 1 to 4, there is an arithimetic series developing

The formula for arithmetic series is: n(n+1)/2

i.e. (n^2 + n) / 2

For a big oh, calculation, we reduce an equation down to its largest increasing component i.e. n^2.

=> O(n^2) ANSWER

I was really looking for an alternative way to understand so I can approach any big oh question with confidence, If i get that i will award full marks , as i said these are practice questions for this week and our lecturer can be very creative, examples with walkthroughs would be great

Let's start by going over what the purpose of Big-O notation is, because I've seen entirely too many computer science classes where they explain the mechanics of it without really explaining why this is a useful tool.

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.

0

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

For ii and iii, what assumptions are you making about m?
n+m = O(n )
n*m = O(n^2)
Are these the complete and unqualified answers given in last year's tests?

For 2nd problem, what if you start with n = 100, and then consider doubling to n = 200.

>> The third loop is a logical check and adds no variable
Does this means that you can discard the third loop because there is no increase in the operations associated with this loop?

0

Indie101Author Commented:

Hi Phoffric,

Yes those were the answers for ii and iii, they were the answers given, just that addition was different to multiplication, in terms of Big Oh,

I dont know if you can discard the third loop,

As i said I have an exam which features on a module I'm doing, I work as a server support etc, I'm not a programmer, hence me asking on this forum, any walkthrough would be great

>> (iii) Multiplying an n-digit number by an m-digit number
So, there were no qualifying remarks about 'm', and the answer did not have 'm' in it. In that case, maybe 'm' is a constant?? If so, suppose n = 100 and m = 2. Then there are 200 multiplies using pencil and paper. Then there are about 200 additions (i.e., a total of 200 x and 200 + operations).

Then if we double n to be n = 200, then there are 400 x and 400 + operations. So, holding m constant means that the number of operations has doubled which means that the complexity is O(n). If the problem deals with both n and m doubling, that is another problem to consider.

A walk through on the 2nd problem is a good idea.
>> if ( j % i == 0 ) {

For a given value of n, you hit this line how many times? If you double n, then how does that affect the number of times you hit this line?

After answering this, then ask the same two questions for how often the expression (j % i == 0) will be true. If you double n, does this expression become true more often?

Now how often the expression becomes true affects the hitting of this line:
>> for ( int k = 0; k < j; k ++ ) {

In the modified code below, the if condition is commented out. In this case, what is the complexity of this program? If n = 10000 and you increase n 10-fold to 100000, and then again 10-fold to 1000000, how does the cpu time increase? We could time it and see if the results match our expectations.

You say the test answer gives for this 2nd question:
=> O(n^2) ANSWER
I'll have to think about this answer in light of the modified program below.

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); }// } }}

Ok, trickster question. :(
>> if ( j % i == 0 )
Since 0 < j < i, then j%i is 0 only when j == i.
I was looking too fast and was thinking (i % j).

I don't like trickster stuff in questions like this for complexity topics - it is sometimes hard enough to get through some of the difficult parts of complexity without having to deal with the trickster stuff.

So, using this information, you can explicitly address the questions above without commenting out the code.

For practice, you can address the questions above with the code commented out.

0

Featured Post

Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.