Skip to main content
Software Engineering

Return to Question

Tweeted twitter.com/#!/StackProgrammer/status/501044764423491585
transliterated the image to plain text
Source Link
amon
amon
  • 135.9k
  • 27
  • 295
  • 386

I have this question which I need answered: enter image description here

What is the asymptotic running time for the following piece of code?

if (N < 1000)
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      A[i] = j;
else
  for (int i = 0; i < N; i++)
    A[i] = i;
  1. logarithmic in N
  2. linear in N ()
  3. linearithmic in N
  4. quadratic in N

And the correct result is "B: Linear in N"“2. linear in N” which I can't figure out why, since that as far as I've understood, we want to accept the worst case>best case. 

The worst case here is that the if statement is run and the time would then be quadracticquadratic in N. I am aware that we're trying to find some kind of average of more attempts, but how can I know what the value of N is? If N is really high (10000), it's obviously the else statement that is run most of the times. But can we assume this or have I misunderstood something? Thanks in advance.

I have this question which I need answered: enter image description here

And the correct result is "B: Linear in N" which I can't figure out why, since that as far as I've understood, we want to accept the worst case>best case. The worst case here is that the if statement is run and the time would then be quadractic in N. I am aware that we're trying to find some kind of average of more attempts, but how can I know what the value of N is? If N is really high (10000), it's obviously the else statement that is run most of the times. But can we assume this or have I misunderstood something? Thanks in advance.

I have this question which I need answered:

What is the asymptotic running time for the following piece of code?

if (N < 1000)
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      A[i] = j;
else
  for (int i = 0; i < N; i++)
    A[i] = i;
  1. logarithmic in N
  2. linear in N ()
  3. linearithmic in N
  4. quadratic in N

And the correct result is “2. linear in N” which I can't figure out why, since that as far as I've understood, we want to accept the worst case>best case. 

The worst case here is that the if statement is run and the time would then be quadratic in N. I am aware that we're trying to find some kind of average of more attempts, but how can I know what the value of N is? If N is really high (10000), it's obviously the else statement that is run most of the times. But can we assume this or have I misunderstood something?

Source Link
owwyess
owwyess
  • 145
  • 1
  • 1
  • 8

Asymptotic running time of for-loops

I have this question which I need answered: enter image description here

And the correct result is "B: Linear in N" which I can't figure out why, since that as far as I've understood, we want to accept the worst case>best case. The worst case here is that the if statement is run and the time would then be quadractic in N. I am aware that we're trying to find some kind of average of more attempts, but how can I know what the value of N is? If N is really high (10000), it's obviously the else statement that is run most of the times. But can we assume this or have I misunderstood something? Thanks in advance.