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)
10 4362
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
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
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.
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)
Yep, that's correct.
kind regards,
Jos
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
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
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
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
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
Sign in to post your reply or Sign up for a free account.
Similar topics
by: Edg Bamyasi |
last post by:
This Is A Late Cross Post from comp.lang.python. It seems the mistery
is deeper then i expected.
What is the running time of conactination on character strings.
i.e.
>> joe="123"
>>...
|
by: Ken |
last post by:
Hi.
Can anyone refer me to any articles about the compatibility between
c++ polymorphism and real-time programming?
I'm currently on a real-time c++ project, and we're having a
discussion...
|
by: junky_fellow |
last post by:
How do we calculate the complexity of an algorithm?
Am i right if i say the complexity of an algorithm
is the number of comparisons done in that algorithm?
thanx in advance .......
|
by: ben |
last post by:
hello,
i'm following an algorithm book and am stuck on an early excersise in
it, not because of the c programming side of it or even the algorithm
side of it, i don't think, but because of maths....
|
by: vashwath |
last post by:
Might be off topic but I don't know where to post this question.Hope
some body clears my doubt.
The coding standard of the project which I am working on say's not to
use malloc.When I asked my...
|
by: Razzel |
last post by:
I created this as a test:
#include <time.h>
main(){
printf(X1: %s\n", putim());
printf(X2: %s\n", putim());
}
putim() {
time_t t;
time(&t);
return(ctime(&t));
|
by: pjhyett |
last post by:
standard 2d array filling with increasing numbers for rows and columns:
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
a = i + j;
problem is it's O(n^2). I'm looking for a method to decrease the...
|
by: Lionel B |
last post by:
Hi,
Anyone know if the Standard has anything to say about the time complexity
of size() for std::set?
I need to access a set's size (/not/ to know if it is empty!) heavily
during an algorithm...
|
by: desktop |
last post by:
In the C++ standard sec 23.1.2 table 69 it says that erase(q) where q is
a pointer to an element can be done in amortized constant time.
I guess that is not worst case since std::set is...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
| |