Can somebody tell me the efficiency of the following:

[Shilpa Sethi]

1. Factorial program using

a. Iteration
b. Recursion

2.

for(int i = 0; i < 3; i++) { //linear
            for(int j = 0; j < 4; j ++){ // log (n)
                    //do constant time stuff
            }
    }

Will it be O(12) or something else?

3.

for(int j = 0; j < n; j *= 2){ 
            //do constant time stuff
    }

and

for(int j = 0; j < n; j *= 10){ 
            //do constant time stuff
    }

Does the big-O automatically become O(logN)?

5.

for(int i = 0; i < n*n; i++) {
            cout << i << endl;
    }

Will it be O(n^n) or O(n) only.

[Oralloy]

Shilpa,

We won't do your homework for you.

Think about the answers, write what you think, then ask. That's how this site works. Don't worry, you'll get lots of help.

Cheers!

p.s. #1 is tricky, the rest are trivial. Think about how a Turing machine works. Then, think about techniques for computing mathematic values. Be sure to state your assumptions.

:)

[Shilpa Sethi]

Hi Oralloy,

Thanks for your prompt reply. However neither I am a student nor is this any of my homework exercise.

I was reading articles on calculating efficiency and some doubts arose in from there. I am little confused, so have even given the options with them.

I am new to calculating efficiency, so please request you to help me out in clearing my doubts.

Thanks,
Shilpa.

[Nepomuk]

Hi Shilpa!

As every student could claim to not be one, we have no way of knowing if you are one or not. However, I'll give you a few tips that I would also feel comfortable giving you if you were a student.

The big O notation (or Landau notation) only gives rough estimates. In general, f in O(x) with x being dependent on n means that there's a real number a so that f takes a maximum of a*x steps. It doesn't matter if a is 2 or 1000000, that's the same in big O notation. Oh, and you normally take the minimum x for which this is true. So you could write O(2n) and then a may be 3, but you could just as well write O(n) with a=6, the latter being the generally used form.

A tip about the first example: Think about, how you would implement the calculation of n! through iteration and recursion. How many steps would it take with either approach?

Oh by the way, and I'm assuming you're talking about time efficiency, not space efficiency? The Big O notation works for both, but your answers suggest time and that is often the one you're more likely to talk about when learning about algorithms.

Greetings,
Nepomuk

[jkmyoung]

1. This really depends on if you're counting the number of bit operations, or using a larger abstract datatype like a int16 or int64.

Further, there are many different ways to implement this operation. eg one example could include the following (tries to reduce number of bit multiplications): Find 10!

2*3 = 6 (store on stack)
4*5 = 20 (look at stack, see 6 is lower)
20 * 6 = 120 (store on stack)
6 * 7 = 42 (look at stack, see 120 is bigger, store on stack)
8 * 9 = 72 (look at stack, see 42 is lower)
42 * 72 = 3024 (look at stack, see 120 is lower)
3024 * 120 = 362880
362880 * 10 = 3628800
===
Assuming the basic method,
basic runtime assuming a large enough integer datatype is O(n). However, recursion will take longer due to the function overhead in each recursive step.

2. O(1)

3. Yes.
O (log2(n)) is equivalent to O(log10(n)) is equivalent to O(log(n))


5. Try some examples. eg n = 1, 2, 3, 4, 5, 10, 50, 100, and see your results.