Solved

Big Oh practice questions

Posted on 2010-08-22
8
878 Views
Last Modified: 2012-08-14
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);
}
}
}
}
0
Comment
Question by:Indie101
  • 5
  • 2
8 Comments
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
As this problem is academic in nature, you should show us your attempted solutions, and we can comment on them.
0
 

Author Comment

by:Indie101
Comment Utility
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

0
 
LVL 4

Accepted Solution

by:
QCD earned 500 total points
Comment Utility
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
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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
6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

 

Author Comment

by:Indie101
Comment Utility
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
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
>> (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.
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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);

      }

//  }

  }

}

Open in new window

0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Suggested Solutions

If you haven’t already, I encourage you to read the first article (http://www.experts-exchange.com/articles/18680/An-Introduction-to-R-Programming-and-R-Studio.html) in my series to gain a basic foundation of R and R Studio.  You will also find the …
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The viewer will learn how to implement Singleton Design Pattern in Java.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

763 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now