-2

For the following program fragment you will (a) write down the total work done by each program statement (beside each statement), (b) compute an expression for the total time complexity, T(n) and derive thhe big Oh complexity, showing all steps to the final answer. I am having a lot of trouble starting off.

for ( i = 0; i < n; i++) {

  for ( j = 0; j < 1000; j++) {

    a[ i ] = random(n) // random() takes constant time

    }

}
Davidson
  • 33
  • 3
  • 8
  • 2
    Please don't post homework here. Read up on how to do Big-O, then ask if you have a more specific question if you have a real problem. Read this: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it – Heman Gandhi Feb 04 '16 at 01:49
  • 2
    I'm voting to close this question as off-topic because it is nothing but a lazy homework dump, one that shows no evidence of effort or initiative. – Hovercraft Full Of Eels Feb 04 '16 at 01:50
  • I've tried to do it, I am having so much trouble. For the first line of code, I say it is 'n', but not sure for the rest. – Davidson Feb 04 '16 at 01:55
  • I don't know why the community here is so toxic. I did finish it, but I think it is completely wrong. I had T(n) = O(n) as a result – Davidson Feb 04 '16 at 02:06
  • I believe that's correct @Davidson. The inner loop takes constant time, which would make the total time like O(n*1000), but due to the rule of constant multiplication it simplifies to O(n) – DJanssens Feb 04 '16 at 02:08
  • I have another piece of code i put below, am I right? – Davidson Feb 04 '16 at 02:36

1 Answers1

-1
int sortedArray [];

for ( i = 0; i < n; i++) {

  for ( j = 0; j < i; j++) {

    readArray(a) // reads in an array of n values

    sortedArray = sort(a) // sort() takes n log n operations

    }

}

I also had this problem. On 2nd line I have 'n', 3rd I have n^2, 4th I have n, and on 5th I have n log n. For my time complexity I have O(n^2).

Erick G. Hagstrom
  • 4,873
  • 1
  • 24
  • 38
Davidson
  • 33
  • 3
  • 8