0

I was task with a problem to write a test program to evaluate the computational complexity (Big O) of the following problem and really dont know where to start.

  1. A single loop iterated n times
  2. A nested loop where eaach loop is iterated n times

This is what I was able to produce

for(int i=0; i <n; i++){
   // Do stuff
}

The problem now is how to write the test program. Can someone help me out?

Edd
  • 65
  • 5
  • C-language? you're on the right track. Read more about big-o here http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o – Fredrik Pihl Sep 02 '11 at 20:55
  • 2
    You can't really "evaluate the computational complexity", as big-O notation is defined in terms of the *asymptotic* performance (i.e. it's an algebraic expression for the behaviour as `n` goes to infinity). However, you could run your program for different values of `n`, time it, and plot the results. Is this what you want to do? – Oliver Charlesworth Sep 02 '11 at 20:57

2 Answers2

0

From what you described, the complexity of the algo seems to be O(n ^ 2). It can be possible to try evaluating it "experimentally": just run the algo with different n values and take the computation times. Then plot the n values on the x axis of a graph and the time values on the y axis. You should now see something approximable with a parabola.

Simone
  • 2,261
  • 2
  • 19
  • 27
0

For problems with complexities of the form (n^k) where k>=0 , code can be written by counting number of nested loops . But it's difficult to implement in recursive problems with "complex" complexities ( (n^2)*lg(n) ).

I have not implemented it ,but i am sure ,can be done

abhi120
  • 278
  • 4
  • 15