473,320 Members | 1,699 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

how to calculate time comlexity of the given algorithm code

#include<iostream>
#include<stdlib.h>
using namespace std;

int main(){
int i, j, n;
for(i=0;i<n; i++){

for(j=0; j<n; j++){
cout<<"my time complexity is = "<<i*j<<endl;
}
cout<<"complexity is increasing"<<j<<endl;
}
system("pause");
return 0;
}
Nov 8 '08 #1
7 3545
JosAH
11,448 Expert 8TB
For any value of n >= 0 your outer loop body runs n times and your inner loop
body runs n*n times so O(n^2) is the big-Oh value.

kind regards,

Jos
Nov 8 '08 #2
Ganon11
3,652 Expert 2GB
Of course, if you put this code into your compiler and run it, you have no idea what will happen, since you never give a value to n.

In general, most loops will have a complexity of O(n) where n is the difference between the initial value and the final value of the index. Most for loops start at 0 or 1 and end at some variable value like n, or size, or so on.

Be careful, though, as some loops are tricky. The following loop, for example, is not O(n) but in fact O(log n):

Expand|Select|Wrap|Line Numbers
  1. for (int i = myList.size(); i > 0; i/=2) {
  2.    // ...
  3. }
Nov 8 '08 #3
JosAH
11,448 Expert 8TB
Be careful, though, as some loops are tricky. The following loop, for example, is not O(n) but in fact O(log n):

Expand|Select|Wrap|Line Numbers
  1. for (int i = myList.size(); i >= 0; i/=2) {
  2.    // ...
  3. }
If there's no 'break' or 'return' in the body of that loop it actually is a 'dynamic halt',
i.e. it never ends, it is O(infinity) ;-)

kind regards,

Jos
Nov 8 '08 #4
Ganon11
3,652 Expert 2GB
Well, if you treat i as a floating point number - then it would eventually get to 0.5, 0.25, 0.125, 0.0625, etc... which is an infinite series converging to 0. However, because C/C++ get easily confused with floating points and ints, they say, "Meh, with ints, 1/2 is 0."
Nov 8 '08 #5
Ganon11
3,652 Expert 2GB
Or I could realize that I said i >= 0, and 0/2 is 0...
Nov 8 '08 #6
JosAH
11,448 Expert 8TB
Or I could realize that I said i >= 0, and 0/2 is 0...
:-) yep, that was what I was pointing at.

kind regards,

Jos
Nov 8 '08 #7
donbock
2,426 Expert 2GB
The OP didn't actually ask a question, except in the title of the post. By "time complexity" did you mean big-oh, such as O(n^2)? All of the replies were based on inspection of the source code; do you need to obtain an answer by executing the code?
Nov 8 '08 #8

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

Similar topics

7
by: MIA | last post by:
Hi, I have an nxn array in which in each row is consisting of +ve and -ve numbers, such that -ve number comes before +ve numbers. e.g. -45 | -9 | -3 | 2 =================== -5 | -9 | 21 |...
3
by: CrystalDBA | last post by:
I am using SQL Server 2000. I need to query my database for all the contracts that came in during a certain time frame (user is prompted for reportingperiodid). Table - Periods Fields -...
6
by: Herrcho | last post by:
in K&R Chapter 6.3 it mentions two methods to calculate NKEYS. and points out the first one which is to terminate the list of initializers with a null pointer, then loop along keytab until the...
7
by: carterweb | last post by:
This is how I do it now. 1. Determine the dimensions of the rectangle. 2. Set a my font size to a fixed maximum size. 3. Apply the font my string and measure the string using the graphics...
37
by: mazwolfe | last post by:
I'm new here, so excuse me if my style is incorrect. Can anyone come up with a better method for this calculation? Code: int is_leap(int year) { switch (year % 19) { case 0: case 3: case 6:...
5
by: Michael R. Copeland | last post by:
I need to determine a given date's week number, but my searches of google only confuse and frustrate me: there are many apparent formulas (which are pretty complex) and they all seem to require...
3
by: victorporton | last post by:
D.K. is traveling from City A to City B. He can stop at some designated spots only. I am trying to use Dijkstra’s algorithm to determine the “spot-to-spot” path that will get D.K. from City A to...
2
by: Manogna | last post by:
hi! all, in a directory nearly 10 zipped file are available. totally the size of the all files is nearly 15GB. i have to retrive the line which dont have the text "ORA" from each file...
1
by: Michel | last post by:
Hello, I need to calculate moving averages of weekly data during the last year. After some search, I believe that the best approach will be to get a dataset from the SQL Server database, browse...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

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.