Hi ;
I just wanted to verify why we are ignoring the time complexity of the iteration itself? meaning with this
lets say I have a for loop like
for (int i=0;i<60;i++)
{
printf("hello world");
}
so why when we want to calculate the time complexity of for we are ignoring the time of the iteration itself? we are just looking on the time complexity of operation "printf("hello world")" ..what about the time of iteration itself regardless of what's inside the iteration ....isn't it taking time also? or simply we are assuming the time of iteration itself is zero for convenient ?

thanks for your help

 

When you put a time counter, for example, in a loop you are measuring the execution
time of the whole loop. The loop iterates and each time it does all its housekeeping
tasks like the incrementing of loop test variable, the test itself, and all the code inside
the loop. So your time counter is measuring all the instruction cycles being executed
by loop and in loop.

So when you exit, the the counter has the total number of cycles used. However that
is not necessarily the same as time because of things like interrupts, variable rollover,
test variable time difference between success (exit) and fail (continue).

To measure just loop and internal code time you would read ASM file output and count
instruction cycles.


Regards, Dana.

 

Hi ;
I just wanted to verify why we are ignoring the time complexity of the iteration itself? meaning with this
lets say I have a for loop like
for (int i=0;i<60;i++)
{
printf("hello world");
}
so why when we want to calculate the time complexity of for we are ignoring the time of the iteration itself? we are just looking on the time complexity of operation "printf("hello world")" ..what about the time of iteration itself regardless of what's inside the iteration ....isn't it taking time also? or simply we are assuming the time of iteration itself is zero for convenient ?

thanks for your help

What you wrote has constant running time. But let's say that instead you had written

for ( int i = 0; i < n; ++i )
  printf( "hello, world.\n" );

The complexity of the code above is linear in n. Setting up the loop has a one-time constant cost, independent of the size of n, so we don't care about it. The printf() call has some constant computational cost associated with it, but since we are calling it n times, its cost depends on n.

 

Lastly the time of setting up and iterating the loop is flyspecks in the pepper compared to the time it takes to do printf which may or may not be constant on any reasonable modern system.

 

Lastly the time of setting up and iterating the loop is flyspecks in the pepper compared to the time it takes to do printf which may or may not be constant on any reasonable modern system.

Do you mean that the time of setting up is mingled/included in the command printf's time?!

 

What you wrote has constant running time. But let's say that instead you had written

for ( int i = 0; i < n; ++i )
  printf( "hello, world.\n" );

The complexity of the code above is linear in n. Setting up the loop has a one-time constant cost, independent of the size of n, so we don't care about it. The printf() call has some constant computational cost associated with it, but since we are calling it n times, its cost depends on n.

firstly thank you !

secondly, why don't we care about one time constant? and how do you know that setting up the loop has a one time constant and maybe it's unstable no?
what are the calculations that you're doing for determining what's time complexity and which arguments to care about and which not?

 

Hi ;
I just wanted to verify why we are ignoring the time complexity of the iteration itself? meaning with this
lets say I have a for loop like
for (int i=0;i<60;i++)
{
printf("hello world");
}
so why when we want to calculate the time complexity of for we are ignoring the time of the iteration itself? we are just looking on the time complexity of operation "printf("hello world")" ..what about the time of iteration itself regardless of what's inside the iteration ....isn't it taking time also? or simply we are assuming the time of iteration itself is zero for convenient ?

thanks for your help

What is it you are trying to measure the time complexity of?

What is the purpose for executing the loop 60 times? Is it to make the whole thing take enough time so that you can get a decent measurement? If so, then what you are probably measuring the time complexity of is just the printf() call and the loop is a means to an end.

If you want to measure the time complexity of the whole thing then it will be a constant. Remember, time complexity is a measure of how the execution time grows as the size of the problem grows. You don't have a problem that can grow. You are always executing a loop 60 times and each pass in the loop is always printing out the same string.

 

Be careful about measuring time as C has a memory manager and
that coupled with stack operations can lead one to a false conclusion
about time. The same piece of code can show different times.

That's why counting code instruction cycles in the ASM
code, although tedious, is one of the better ways of measuring time
to do some code execution.

Another way of doing this is with a scope and toggling a pin in loop. In fact
put scope on infinite persistence and time jitter due to all these other
issues will be shown.

Regards, Dana

 

Do you mean that the time of setting up is mingled/included in the command printf's time?!

NO!! I'm saying printf takes 99.9% of the total time. The remainder, 1 part in 1000, is almost immeasurable.

 

firstly thank you !

secondly, why don't we care about one time constant? and how do you know that setting up the loop has a one time constant and maybe it's unstable no?
what are the calculations that you're doing for determining what's time complexity and which arguments to care about and which not?

In the context of time complexity of an algorithm, constants don't matter because we only care about how the algorithm scales with its input. Remember, the point of quantifying algorithmic complexity is so that we can make apples-to-apples comparisons with other algorithms. Many factors will influence the real-world performance of any particular algorithm -- processor speed, word length, the size of memory caches, etc. -- but all of these are external to (and independent of) the algorithm itself. So, instead of writing a general expression that includes these external factors (e.g., f(n) ~ An^3 + Bn^2 + C), we strip away everything except the dominant term in the algorithm's behavior (e.g., f(n) ~ n^3). This is what's important because, as the input gets very large, the values of any lower order terms (especially constants) get swamped.

 

NO!! I'm saying printf takes 99.9% of the total time. The remainder, 1 part in 1000, is almost immeasurable.

got you .. when we are deciding to don't care about things and comparing which one is takes time bigger than other command? meaning maybe there's any definition for "don't care" and when we should say don't care ..

secondly, who decide the setting up is smaller than the printf command? I think here also I miss understanding the concept when we should care and when we shouldn't .. maybe if you elaborate please about the "concept of" will be more clearly

 

In the context of time complexity of an algorithm, constants don't matter because we only care about how the algorithm scales with its input. Remember, the point of quantifying algorithmic complexity is so that we can make apples-to-apples comparisons with other algorithms. Many factors will influence the real-world performance of any particular algorithm -- processor speed, word length, the size of memory caches, etc. -- but all of these are external to (and independent of) the algorithm itself. So, instead of writing a general expression that includes these external factors (e.g., f(n) ~ An^3 + Bn^2 + C), we strip away everything except the dominant term in the algorithm's behavior (e.g., f(n) ~ n^3). This is what's important because, as the input gets very large, the values of any lower order terms (especially constants) get swamped.

But the constant time .. is also time , why wouldn't care about? still confused !! I can say and save in my head constant time = don't care .. but I want to understand " why " we are neglecting this time although we are calculating "time" something going wrong here !!

 

got you .. when we are deciding to don't care about things and comparing which one is takes time bigger than other command? meaning maybe there's any definition for "don't care" and when we should say don't care ..

secondly, who decide the setting up is smaller than the printf command? I think here also I miss understanding the concept when we should care and when we shouldn't .. maybe if you elaborate please about the "concept of" will be more clearly

In the days before the electronic calculator hit the market at less than $100.00 in the early 1970's we used to do complex calculations with a slide rule. It was quick and you could get 3-4 signifcant digits with high confidence. Three significant digits represents 1 part in 1000, and Four significant digits represents 1 part in 10,000. Somewhere in between is the "don't care" area.

To answer the other question of how do we know that the "setup" time is insignificant, we can turn to the compiler output which will display the assembly language instructions for setting up the loop, calling printf, WAITING while each character is printed, and finally exiting the loop. We count those instructions whose execution time is well known and we also know how long it takes to "print" a character. I have actually done this and so I know the answer. On a hypothetical processor with an instruction execution time of 1 microsecond (slow in todays universe) and a "printer" which takes a bit over 1 millisecond (which has not changed much in 50 years) and you get the ratio of 1 to 1000. Make the processor faster and the ratio can easily approach 1 in 10,000.

I have had a career spanning over 60 years and I have seen a thing or two.

 

But the constant time .. is also time , why wouldn't care about? still confused !! I can say and save in my head constant time = don't care .. but I want to understand " why " we are neglecting this time although we are calculating "time" something going wrong here !!

Two different things with two different goals. If you're interested in comparing different algorithms -- not their implementations but the algorithms themselves -- it's best to use complexity analysis (big-O and friends), because this abstracts away all the details that depend on any chosen implementation. On the other hand, if you want to know how a particular algorithm performs on a specific machine using a specific data set, you implement and time it -- this will include all the constants and stuff that the complexity analysis doesn't care about.

One is not better than the other, they're just different types of metrics. Complexity analysis generalizes the notion of performance, which makes it widely applicable but removes a bunch of detail; raw timing gives us all the detail, at the expense of not being applicable in wider contexts. To see why raw timing (or including all the constants and such in a complexity analysis) has such narrow focus, consider that many algorithms are highly sensitive to the hardware architecture on which they run. What if you time a sorting algorithm on an 8-bit microcontroller with a single-cycle processor and 8 kB of cache and find that it takes 24 seconds to run. Running the same algorithm on the same data may take 24 ms on a 64-bit superscalar CPU with 8 MB of L1 cache. That's a factor of a 1,000 in performance difference, for the same algorithm! Clearly such a test is more a reflection of the underlying hardware than the algorithm itself, so it wouldn't be useful to compare the raw timing performance of one algorithm against the raw timing performance of another algorithm on a different machine.

That's why we use complexity analysis to characterize algorithm performance, and benchmarks to characterize hardware performance.

 

What is it you are trying to measure the time complexity of?

What is the purpose for executing the loop 60 times? Is it to make the whole thing take enough time so that you can get a decent measurement? If so, then what you are probably measuring the time complexity of is just the printf() call and the loop is a means to an end.

If you want to measure the time complexity of the whole thing then it will be a constant. Remember, time complexity is a measure of how the execution time grows as the size of the problem grows. You don't have a problem that can grow. You are always executing a loop 60 times and each pass in the loop is always printing out the same string.

Hi WBahn , THANK you for your help along my discussions in the forums at all.
Secondly, frankly I didn't understand you , then why we neglect the time of setting up the loop ? is it because we care how time complexity grows? and how I'm going always to what's inside the loop for calculating the time complexity neglecting the setting of the loop itself in every iteration? what do you mean by a measure of how the execution time grows? you mean we are not looking for the exact decent time ?! thanks !
Maybe because I have wrong pre-concepts I found it hard to understand ! I hope that you help me to organize correctly the whole things up

 

lets say I have code like this :
while (i<10)
{
printf("hi");
}
so the program will enter the while 10 times, but what about the last call on i=11 which will not enter the while loop? why we don't care about it ... and here I deeply reckon that I still miss understanding the concept of "don't care" ! any help?!

 

The time attributed to loop control and tests for exit usually small compared to
what you are doing inside loop. Like calling functions, stack operations, "normal"
inline code execution.

In a tight loop, say where you set a flag and that's it, then loop control and execution
are an appreciable part of the time to execute. Whereas in a loop where several f()
calls are made (lots of stack push happens then the actual f() code executes, then stack
pulls). In this case loop control and conditional test for exit are trivial portion of execution
time.

You can do simple code, look at ASM file, then do case for calling f()s inside loop, again
look at ASM file, to see these effects.

Regards, Dana.

 

Hi WBahn , THANK you for your help along my discussions in the forums at all.
Secondly, frankly I didn't understand you , then why we neglect the time of setting up the loop ? is it because we care how time complexity grows? and how I'm going always to what's inside the loop for calculating the time complexity neglecting the setting of the loop itself in every iteration? what do you mean by a measure of how the execution time grows? you mean we are not looking for the exact decent time ?! thanks !
Maybe because I have wrong pre-concepts I found it hard to understand ! I hope that you help me to organize correctly the whole things up

If you want to measure the thickness of a sheet of paper, you will probably have some difficulty measuring something so thin without special tools and, even then, getting a measurement of high accuracy might be very difficult.

So instead you might stack together 10,000 pieces of paper, measure the height of the stack with even a fairly crude instrument, and divide by 10,000 to get a pretty decent measurement of the average thickness of a single piece of paper.

So if I want to measure how long it takes to execute the printf() statement, I might not be able to get good enough timing information with a single execution, so instead I put it in a loop and execute it a lot of time and measure how long all of them combined take and divide that time by the number of times the loop was executed in order to get the average time to execute the printf() once.

So that's one reason why someone might run that loop you presented -- they only want to know how long the printf() statement takes to execute and the loop is just there to make the measurement better.

But what if the loop IS the point of the code -- for some reason someone wants to print "hello world" sixty time -- and they want to know how long that takes. Now the loop is part of the code being measured, so you would NOT divide the measurement by sixty.

But in either case the time is still a constant.

 

lets say I have code like this :
while (i<10)
{
printf("hi");
}
so the program will enter the while 10 times, but what about the last call on i=11 which will not enter the while loop? why we don't care about it ... and here I deeply reckon that I still miss understanding the concept of "don't care" ! any help?!

You keep using programs that are of constant complexity, which is making it hard for you to understand why we normally don't care about constant-complexity COMPONENTS of programs.

If the constant term is the dominant term, then we DO care about it. In general, we care ONLY about the dominant term whatever it turns out to be.

Let's say that we have two sorting algorithms that have the following expressions for T(n):

T1(n) = 5·n² + 100·n + 10,000,000

T2(n) = 1,000,000,000·n + 10,000

Which term dominates the time taken by each algorithm as the size of the data set grows?

Which algorithm is faster as the size of the data set grows?

Let's look at that first question first and look just at T1(n).

T(1) = 10,000,105 and clearly the time is completely dominated by the constant term accounting for 99.999% of the total time.
T(1,000) = 15,100,000 and the constant term now only accounts for about 66% of the total time.
T(10,000) = 511,000,000 and now the constant term only accounts for less than 2% of the total time and the quadratic term accounts for nearly 98% of the time.
T(1,000,000) = 5,000,110,000,000 and now the quadratic term accounts for 99.998.

As n gets larger, I can completely ignore everything except the dominant term and get a very good estimate of how long it will take to execute.

Similarly, if I want to compare T1(n) to T2(n) for large values of n, I see that the 1,000,000,000 factor in front of the n term in T2 just doesn't matter in the end.

T1(1) = 10,000,105
T2(1) = 1,000,010,000
T1/T2 = 0.01

T1(1,000) = 15,100,000
T2(1,000) = 1,000,000,010,000
T1/T2 = 0.000015

T(1,000,000) = 5,000,110,000,000
T2(1,000,000) = 1,000,000,000,010,000
T1/T2 = 0.005

T1(1,000,000,000) = 5,000,000,100,010,000,000
T2(1,000,000,000) = 1,000,000,000,000,010,000
T1/T2 = 5

T(1,000,000,000,000) = 5,000,000,000,100,000,010,000,000
T2(1,000,000,000,000) = 1,000,000,000,000,000,010,000
T1/T2 = 5,000

And as n grows further T1 takes more and more time.

As to why big-O drops the coefficient of the dominant term, that has to do with the desire to explore the growth function of a given algorithm as n grows.

Let's say that we have

T(n) = An² + Bn + C

We want to know how the running time increases as we double the size of the data set.

T(2n) / T(n)

[A(2n)² + B(2n) + C] / [An² + Bn + C]

[4An² + 2Bn + C] / [An² + Bn + C]

Divide top and bottom by An² and you get

[4 + B/(2An) + C/(4An²)] / [1 + B/(4An) + C/(4An²)]

As n grows, all of the terms that have n in them are driven toward zero, leaving only

T(2n) / T(n) = 4 in the limit as n grow arbitrarily large.

Notice that the value of NONE of the coefficient terms mattered at all. The only impact that they have is determining the specific size of n beyond which we can declare that they no longer have a significant effect -- but all we care about is that there IS a size of n beyond which they have no significant effect.

 

You keep using programs that are of constant complexity, which is making it hard for you to understand why we normally don't care about constant-complexity COMPONENTS of programs.

If the constant term is the dominant term, then we DO care about it. In general, we care ONLY about the dominant term whatever it turns out to be.

Let's say that we have two sorting algorithms that have the following expressions for T(n):

T1(n) = 5·n² + 100·n + 10,000,000

T2(n) = 1,000,000,000·n + 10,000

Which term dominates the time taken by each algorithm as the size of the data set grows?

Which algorithm is faster as the size of the data set grows?

Let's look at that first question first and look just at T1(n).

T(1) = 10,000,105 and clearly the time is completely dominated by the constant term accounting for 99.999% of the total time.
T(1,000) = 15,100,000 and the constant term now only accounts for about 66% of the total time.
T(10,000) = 511,000,000 and now the constant term only accounts for less than 2% of the total time and the quadratic term accounts for nearly 98% of the time.
T(1,000,000) = 5,000,110,000,000 and now the quadratic term accounts for 99.998.

As n gets larger, I can completely ignore everything except the dominant term and get a very good estimate of how long it will take to execute.

Similarly, if I want to compare T1(n) to T2(n) for large values of n, I see that the 1,000,000,000 factor in front of the n term in T2 just doesn't matter in the end.

T1(1) = 10,000,105
T2(1) = 1,000,010,000
T1/T2 = 0.01

T1(1,000) = 15,100,000
T2(1,000) = 1,000,000,010,000
T1/T2 = 0.000015

T(1,000,000) = 5,000,110,000,000
T2(1,000,000) = 1,000,000,000,010,000
T1/T2 = 0.005

T1(1,000,000,000) = 5,000,000,100,010,000,000
T2(1,000,000,000) = 1,000,000,000,000,010,000
T1/T2 = 5

T(1,000,000,000,000) = 5,000,000,000,100,000,010,000,000
T2(1,000,000,000,000) = 1,000,000,000,000,000,010,000
T1/T2 = 5,000

And as n grows further T1 takes more and more time.

As to why big-O drops the coefficient of the dominant term, that has to do with the desire to explore the growth function of a given algorithm as n grows.

Let's say that we have

T(n) = An² + Bn + C

We want to know how the running time increases as we double the size of the data set.

T(2n) / T(n)

[A(2n)² + B(2n) + C] / [An² + Bn + C]

[4An² + 2Bn + C] / [An² + Bn + C]

Divide top and bottom by An² and you get

[4 + B/(2An) + C/(4An²)] / [1 + B/(4An) + C/(4An²)]

As n grows, all of the terms that have n in them are driven toward zero, leaving only

T(2n) / T(n) = 4 in the limit as n grow arbitrarily large.

Notice that the value of NONE of the coefficient terms mattered at all. The only impact that they have is determining the specific size of n beyond which we can declare that they no longer have a significant effect -- but all we care about is that there IS a size of n beyond which they have no significant effect.

Got you and appreciate your help much!!
but last thing lets assume there's a command like int x=3+5 ; then will reading the number "3" and "5" also taking into account for time complexity?! or we look at the command "generally" and determining what's his time complexity of the command without getting deeply of what's going while reading numbers etc .. ?! thanks!!

for example of what I've explained above:
lets assume I have T(n-3) , is that meaning it's the time of T(n-3) also including the time of reading the "argument" n-3 itself?! because reading arguments/variables also takes a time.

I don't know why am I falling into those deeply things but I guess it's a good learning