473,883 Members | 1,750 Online

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

20 New Member
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

for i =10 to -10
for j =-10 to 10
d = sqrt (i+j)
puetpixel (i,j,1)
Oct 15 '08 #1
10 4389
JosAH
11,448 Recognized Expert MVP
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
Oct 15 '08 #2
kinannawaz
20 New Member
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)
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
Oct 16 '08 #3
RedSon
5,000 Recognized Expert Expert
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.
Oct 16 '08 #4
kinannawaz
20 New Member
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)
Oct 22 '08 #5
JosAH
11,448 Recognized Expert MVP
Yep, that's correct.

kind regards,

Jos
Oct 22 '08 #6
kinannawaz
20 New Member
What will be the time complexity of the following code?

Expand|Select|Wrap|Line Numbers
1. for (i=0 to i<10)     =>n+1
2.   for(j=0 to j<10)    =>n(n+1)
3.       x=i+j              => n
4.
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
Oct 25 '08 #7
JosAH
11,448 Recognized Expert MVP
What will be the time complexity of the following code?

Expand|Select|Wrap|Line Numbers
1. for (i=0 to i<10)     =>n+1
2.   for(j=0 to j<10)    =>n(n+1)
3.       x=i+j              => n
4.
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
Oct 25 '08 #8
kinannawaz
20 New Member

here is tricky one

Expand|Select|Wrap|Line Numbers
1. for(i=0 to i<10)
2.  for(j=0 to j<i)
3.     x=i+j
4.
what will be time complexity of each statment and whole code?

Thank you very much
kinnan
Oct 26 '08 #9
JosAH
11,448 Recognized Expert MVP

here is tricky one

Expand|Select|Wrap|Line Numbers
1. for(i=0 to i<10)
2.  for(j=0 to j<i)
3.     x=i+j
4.
what will be time complexity of each statment and whole code?

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
Oct 26 '08 #10