Solved

# Big Oh practice questions

Posted on 2010-08-22

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

}

}

}

}