Solved

Big Oh practice questions

Posted on 2010-08-22
8
906 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
ID: 33495768
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
ID: 33495863
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
ID: 33496838
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
Salesforce Has Never Been Easier

Improve and reinforce salesforce training & adoption using WalkMe's digital adoption platform. Start saving on costly employee training by creating fast intuitive Walk-Thrus for Salesforce. Claim your Free Account Now

 
LVL 32

Expert Comment

by:phoffric
ID: 33497287
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
 

Author Comment

by:Indie101
ID: 33497358
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
ID: 33497478
>> (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
ID: 33497513
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
ID: 33497566
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

Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
How to execute a Python program and gather return output in Java 2 49
java example issue 5 46
web project error add remove 1 56
glassfish admin console 1 23
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

730 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