time complexity of algorithm that is a worst idea to draw a

[kinannawaz]

Can any one help me what will be the time complexity in worst case i.e Big Oh of the following algo I need to resolve it i have worked on it but am not able to come up with the final solution .the below algorithm is going to draw a circle any help or suggestion regarding this algo will be hidhly appreciatable

circle (radius)
for i =10 to -10
for j =-10 to 10
d = sqrt (i+j)
if radius -0.5 < d < radius + 0.5
puetpixel (i,j,1)

[JosAH]

There are two loops, one nested in the other. The outermost loop iterates n times
and the innermost loop iterates m times so you take O(n*m) steps. If m == n
then you take O(n^2) steps.

kind regards,

Jos

[kinannawaz]

You have given The time complexity of the whole Algorithm
Thanks

But i dont understand that u have not calculated the timetime complexity of every statment i.e

d = sqrt (i+j)
if radius -0.5 < d < radius + 0.5
puetpixel (i,j,1)

Can u give more detail regarding following steps
First calculate the time complexity of each statment
Then add up or multiply (depending on the statment ) the time coplexity of each statment
Which will give our final Time complexity>

But i am not able to understand is that What will be the time complexity of each Statment


Any help or suggestion regarding this algo will be hidhly appreciatable

[RedSon]

Big O notation is useful when analyzing algorithms for efficiency. For example, the time (or the number of steps) it takes to complete a problem of size n might be found to be T(n) = 4n² − 2n + 2.

As n grows large, the n² term will come to dominate, so that all other terms can be neglected — for instance when n = 500, the term 4n² is 1000 times as large as the 2n term. Ignoring the latter would have negligible effect on the expression's value for most purposes.

Let me repeat that... ignoring the 2n term will have negligible effect on calculating the time it takes to complete an algorithm as n approaches infinity, therefore calculating the time each operation takes is irrelevant since they have virtually no effect on the overall run time of your function.

[kinannawaz]

what will be the time complexity of the following code

for(i=0 to i<10) =>n+1 (total loop iteration+ one to exit the loop)
j=i+1;

is the above right
so time.complexity will be
O(n)

[JosAH]

Yep, that's correct.

kind regards,

Jos

[kinannawaz]

What will be the time complexity of the following code?

for (i=0 to i<10)     =>n+1
  for(j=0 to j<10)    =>n(n+1)
      x=i+j              => n

Is the above time complexity of each statment correct?
What will be the total time complexity of whole code?

n+1+n(n+1)+n

OR

(n+1)*n(n+1)*n

Which is correct? or both are wrong
What will be the correct time complexity?and how?


Thanks
kinnan

[JosAH]

What will be the time complexity of the following code?

for (i=0 to i<10)     =>n+1
  for(j=0 to j<10)    =>n(n+1)
      x=i+j              => n

Is the above time complexity of each statment correct?
What will be the total time complexity of whole code?

n+1+n(n+1)+n

OR

(n+1)*n(n+1)*n

Which is correct? or both are wrong
What will be the correct time complexity?and how?


Thanks
kinnan

If the first loop runs n times so will the second loop; the second loop is started
n times and the innermost statement will be executed O(n*n) times.

kind regards,

Jos

[kinannawaz]

Thanks fo the answers

here is tricky one

for(i=0 to i<10)
 for(j=0 to j<i)
    x=i+j

what will be time complexity of each statment and whole code?
please give some elaboration also.

Thank you very much
kinnan

[JosAH]

Thanks fo the answers

here is tricky one

for(i=0 to i<10)
 for(j=0 to j<i)
    x=i+j

what will be time complexity of each statment and whole code?
please give some elaboration also.

Thank you very much
kinnan

Ok, last one: the body of the inner loop runs 1+2+3 ... +n times which makes
(n*n+n)/2 times which is O(n^2)

kind regards,

Jos

[kinannawaz]

OKAY

But i donot get the answer?

Can i get more detailed answer please

for(i=0 to i<10)  => n
 for(j=0 to j<i)    => (n+n)/2
    x=i+j            => ???

Is the above correct?
Can i get more explanation on the time complexity of the inner loop?
Have u applied some Arithematic series formula?


Thanks
kinnan