473,883 Members | 1,750 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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

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)
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)
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
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
Thanks fo the answers

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?
please give some elaboration also.

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

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

Sign in to post your reply or Sign up for a free account.

Similar topics

3
2321
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" >> joe+="99999999999999999"
18
12608
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 about whether we should allow polymorphism. Our system is not embedded and does not need to be as real-time as, say, a pacemaker. But it does involve updating displays based on radar input. So a need for something close to real-time is desired...
5
3935
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 .......
2
2110
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. i don't really understand what is expected, or really what the question means. could anyone explain what the question's after please? any help much appreciated. thanks, ben. Prove an upper bound on the number of machine instructions required to
38
2581
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 lead(I have just started working) he said we should not use dynamic allocation in real time systems, the code will not run in predictable time period.Can anybody tell what does he mean?Why the execution time becomes unpredictable? Thanks
17
2220
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));
12
8086
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 time, any suggestions? I'm googling for dynamic programming solutions, but not coming up with much.
26
7229
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 and was thus wondering whether I'd be better off tracking the size "manually" or whether that'd be pointless. Thanks,
33
5583
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 practically a red-black tree where insert/delete takes O(lg n) time. Or are there some other explanation for this complexity?
0
9944
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
11154
Oralloy
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, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10762
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
10422
tracyyun
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 protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
9586
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
5807
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
6005
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4622
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4228
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.