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 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
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 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.
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 11,448
Recognized Expert MVP
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
JosAH 11,448
Recognized Expert MVP
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
JosAH 11,448
Recognized Expert MVP
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
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"
>> joe+="99999999999999999"

by: Ken 
last post by:
Hi.
Can anyone refer me to any articles about the compatibility between
c++ polymorphism and realtime programming?
I'm currently on a realtime 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 realtime as, say, a
pacemaker. But it does involve updating displays based on radar
input. So a need for something close to realtime is desired...

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. 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

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
 
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 time,
any suggestions? I'm googling for dynamic programming solutions, but
not coming up with much.

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,

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 redblack
tree where insert/delete takes O(lg n) time. Or are there some other
explanation for this complexity?

by: marktang 
last post by:
ONU (Optical Network Unit) is one of the key components for providing highspeed 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...

by: Oralloy 
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bitfields 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...
 
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...

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, ZWave, WiFi, 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...

by: agi2029 
last post by:
Let's talk about the concept of autonomous AI software engineers and nocode 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...

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 LANtoLAN VPNs.
The last exercise I practiced was to create a LANtoLAN 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...

by: adsilva 
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?

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
 
by: muto222 
last post by:
How can i add a mobile payment intergratation into php mysql website.
 