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

T(n-3) means the maximum time required to solve any problem of size n-3. It doesn't mean anything more or anything less.

Time complexity is inextricably tied to the size of a problem, such as sorting a list of n values or finding whether there is a path that visits every node, without repeats, in a graph of n nodes.

Any problem that lacks a size scaling parameter has a constant time complexity because it is the time required to perform that exact algorithm.

Sorting a list of ten items has constant time complexity. Sorting a list of n items has a nonconstant time complexity that depends on the algorithm used.

 

T(n-3) means the maximum time required to solve any problem of size n-3. It doesn't mean anything more or anything less.

Time complexity is inextricably tied to the size of a problem, such as sorting a list of n values or finding whether there is a path that visits every node, without repeats, in a graph of n nodes.

Any problem that lacks a size scaling parameter has a constant time complexity because it is the time required to perform that exact algorithm.

Sorting a list of ten items has constant time complexity. Sorting a list of n items has a nonconstant time complexity that depends on the algorithm used.

Im totally with you but while assigning into *n-3* it takes time ; doesn't it?

 

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.

Just to verify something, lets assume I have a function like this:
A(n)
{
A(2/n);
}
I know the time is infinite but my question isn't about time, it's about the time complexity equation, is it T(n)=T(n/2) + C or just T(n)=T(n/2), I guess it's the first opition why? because entering a function of A(n) takes a constant time until exit it ... but I just want to how the algorithmicans think !

thanks

 

Im totally with you but while assigning into *n-3* it takes time ; doesn't it?

T(n-3) is NOT a computation that is being timed!

T(n) is a function that describes the maximum time required to run a particular algorithm implementation on any instance of the problem of size n.

That's it. Nothing more, nothing less. It is NOT part of the algorithm being described or timed.

If T(n) = n² + 4

then, for example, for n=5 T(n) = 29 and, since n-3 is 2, T(n-3) for n=5 is 8.

 

"Time to execute" and "time complexity" of a given code segment are entirely different things.

Time complexity is likely for comparing algorithms, or explaining code performance.

Once I compared a bubble sort to the quicksort on a large number strings, maybe 100,000 or so. The bubble sort took 19 hours. The quicksort took 2 seconds. Observing that one is O(n*n) and the other is O(n*logn) provides some insight to this result.

 

"Time to execute" and "time complexity" of a given code segment are entirely different things.

Time complexity is likely for comparing algorithms, or explaining code performance.

Once I compared a bubble sort to the quicksort on a large number strings, maybe 100,000 or so. The bubble sort took 19 hours. The quicksort took 2 seconds. Observing that one is O(n*n) and the other is O(n*logn) provides some insight to this result.

Out of curiosity, how long ago was it that you did this test?

I ask because that seems awfully slow for anything close to a modern machine. I have a homework assignment where students implement seven different algorithms and measure their performance for data sets ranging from 50,000 elements to 300,000 elements and with the initial data randomly ordered, properly ordered, and reverse ordered. On my nearly seven year old lap top bubble sort took 22 seconds on 100,000 elements and 158 seconds on 300,000 (for randomly sorted data). Quicksort, on the other hand, took 20 ms and 66 ms, respectively.

The real key to appreciating the O() of the two algorithms is to note that increasing the data size by a factor of three resulting in bubble sort taking 7.2 times as long (the quadratic order of complexity would predict 9x, which is in the ballpark) while for quicksort it increased it by a factor of 3.3 (which matches almost exactly what the log-linear complexity predicts).

What really interesting for students to see is that a well-implement bubble sort, on already-sorted data, is not only much faster than quicksort, but is several times faster even than the built-in sorting algorithm used by Java, which is about twenty times faster than my implementation of quicksort. This is one of the reasons that bubblesort still finds utility in applications where the data is expected to be almost already sorted.

 

Out of curiosity, how long ago was it that you did this test?

I ask because that seems awfully slow for anything close to a modern machine. I have a homework assignment where students implement seven different algorithms and measure their performance for data sets ranging from 50,000 elements to 300,000 elements and with the initial data randomly ordered, properly ordered, and reverse ordered. On my nearly seven year old lap top bubble sort took 22 seconds on 100,000 elements and 158 seconds on 300,000 (for randomly sorted data). Quicksort, on the other hand, took 20 ms and 66 ms, respectively.

The real key to appreciating the O() of the two algorithms is to note that increasing the data size by a factor of three resulting in bubble sort taking 7.2 times as long (the quadratic order of complexity would predict 9x, which is in the ballpark) while for quicksort it increased it by a factor of 3.3 (which matches almost exactly what the log-linear complexity predicts).

What really interesting for students to see is that a well-implement bubble sort, on already-sorted data, is not only much faster than quicksort, but is several times faster even than the built-in sorting algorithm used by Java, which is about twenty times faster than my implementation of quicksort. This is one of the reasons that bubblesort still finds utility in applications where the data is expected to be almost already sorted.

THANKS BUDDY!!!!!! appreciate much your detailed answer !
What I'm going to ask is, if there's f(n)<Omega(g(n)) then f(n) <C*g(n) , my question is it's enough to find one "C" that satisfy the equation ..why is that right? lets assume I have f(n)=3n+1 and g(n)=n; then just at C=4 (or bigger than 4) then the equation f(n)<C*g(n) is satisfying .. but it's not satisfying at C<4, doesn't that mean any thing? meaning if C>=4 then g(n) is linear equation although the equation doesn't satisfy at C<4, isn't that matter? to elaborate more, doesn't the growth of function matter at which C we chose for satisfying the equation? so it's enough to find any C that satisfy the equation to say it's bigger/smaller than the other function?

 

THANKS BUDDY!!!!!! appreciate much your detailed answer !
What I'm going to ask is, if there's f(n)<Omega(g(n)) then f(n) <C*g(n) , my question is it's enough to find one "C" that satisfy the equation ..why is that right? lets assume I have f(n)=3n+1 and g(n)=n; then just at C=4 (or bigger than 4) then the equation f(n)<C*g(n) is satisfying .. but it's not satisfying at C<4, doesn't that mean any thing? meaning if C>=4 then g(n) is linear equation although the equation doesn't satisfy at C<4, isn't that matter? to elaborate more, doesn't the growth of function matter at which C we chose for satisfying the equation? so it's enough to find any C that satisfy the equation to say it's bigger/smaller than the other function?

The definition of O() only specifies that there exists positive integers C and No such that

f(n) ≤ C⋅g(n)

for all n ≥ No

So it doesn't matter what the value of C is, only that at least one suitable choice exists.

The reason that it doesn't matter is that BigO is primarily intended to describe the growth of a given algorithm (in terms of time in our case) as the size of the problem that that algorithm is being applied to grows.

So we are looking for the ratio of the times for two different values of n in the same T(n) function. The leading coefficient simply cancels out. Look back at the earlier post where I explained this in detail.

 

The definition of O() only specifies that there exists positive integers C and No such that

f(n) ≤ C⋅g(n)

for all n ≥ No

So it doesn't matter what the value of C is, only that at least one suitable choice exists.

The reason that it doesn't matter is that BigO is primarily intended to describe the growth of a given algorithm (in terms of time in our case) as the size of the problem that that algorithm is being applied to grows.

So we are looking for the ratio of the times for two different values of n in the same T(n) function. The leading coefficient simply cancels out. Look back at the earlier post where I explained this in detail.

to close this gap already!

I can say "doesn't it matter what the value of C" means we are checking the growth of the function itself, right?! guess so, then if the equation f(n) < C*g(n) satisfied ; there's assured "at least" one suitable C that satisfy the equation f(n)< C*g(n) , and if not satisfy then there's no C that satisfy the equation !
C*f(n) is a family of groups of {f(n)}, and the growth of f(n) is f(n) itself without any other coefficient, so if any member of groups doesn't satisfy f(n)<C*g(n) then "definitely" f(n) isn't < g(n) ... but if there's at least one member of groups satisfy f(n)<C*g(n) then definitely f(n)=O(g(n)), why? lemme explain , f(n)=O(g(n) means doesn't matter what constant/coefficient your functions have, I'm gonna check the growth of function itself, for checking that, there must be at least one "C" and enough one of N0 that satisfy the equation.

hope I explained it correctly

again, may I have analogous to the coefficient that doesn't matter? for example when I see a coefficient of specific function lets say 3n, then I imagine now on the (x,y) there's a graph of 3n, then I say 2n and n is smaller than n, how could actually 3n be equal to n asymptotic if there's n and 2n which are smaller than 3n?! doesn't make sense ... "here is my problem!!! maybe I MUST NOT going on that approach "

 

The definition of O() only specifies that there exists
The reason that it doesn't matter is that BigO is primarily intended to describe the growth of a given algorithm (in terms of time in our case) as the size of the problem that that algorithm is being applied to grows.

So we are looking for the ratio of the times for two different values of n in the same T(n) function. The leading coefficient simply cancels out. Look back at the earlier post where I explained this in detail.

first, I reckon here's my problem, I'm not finding that the definition of O() is logically about "there exists" C integers and not for all "integers" , but maybe I must just follow the definition without overthink about it?! but it would be not senseable .

second, may you detail about that more by an example "The reason that it doesn't matter is that BigO is primarily intended to describe the growth of a given algorithm (in terms of time in our case) as the size of the problem that that algorithm is being applied to grows"?

thanks!!

 

Again, look back at my prior post.

Let's say Algorithm #1 has T1(n) = 10n² while Algorithm #2 has T2(n) = 5000n².

By how much does the time grow if I double the size of the problem from N to 2N?

For Algorithm #1:

T1(2N) / T1(N) = 10(2N)² / 10(N)² = 4

For Algorithm #2:

T2(2N) / T2(N) = 5000(2N)² / 5000(N)² = 4

They both have the same growth behavior because they are both O(n²).

If we are comparing two different algorithms, then as long as they are not the same BigO class, the lower complexity one will always eventually outperform the higher one, regardless of the coefficients and for exactly the same reason why we can ignore all but the dominant term in T(n) for determining its time complexity.

Only when we are comparing two algorithms of the same time complexity does it matter what the leading coefficients are. But here's the kicker -- it is actually pretty rare for two algorithms to truly have the same time complexity. If we look carefully enough, we usually discover that the dominant terms are slightly different. Where we really see this is when we are looking at new "better" algorithms that are competing with long-established and highly-optimized existing algorithms. As an example, you might look at the time complexity of the best algorithms for finding the integer factorization of a large number.

Now this is all from a theoretical standpoint where we talk about the behavior as the size of the problem grows arbitrarily large. But, in practice, someone implementing an algorithm usually has at least some idea of how big the problems are that their implementation will be called upon to solve. If execution time is even a concern, then they care about the behavior of their implementation of their chosen algorithm on the size of problems they need to apply it too. So here they often care about that coefficient out front and they may also care about some of the asymptotically non-dominant terms because they may well be dominant for smaller problems. It is frequently the case that "faster" algorithms have significant one-time set-up and wrap-up costs compared to "slower" algorithms and until the problem size gets large enough to amortize those one-time costs, the slower algorithm will actually outperform the faster algorithm.

 

Again, look back at my prior post.

Let's say Algorithm #1 has T1(n) = 10n² while Algorithm #2 has T2(n) = 5000n².

By how much does the time grow if I double the size of the problem from N to 2N?

For Algorithm #1:

T1(2N) / T1(N) = 10(2N)² / 10(N)² = 4

For Algorithm #2:

T2(2N) / T2(N) = 5000(2N)² / 5000(N)² = 4

They both have the same growth behavior because they are both O(n²).

If we are comparing two different algorithms, then as long as they are not the same BigO class, the lower complexity one will always eventually outperform the higher one, regardless of the coefficients and for exactly the same reason why we can ignore all but the dominant term in T(n) for determining its time complexity.

Only when we are comparing two algorithms of the same time complexity does it matter what the leading coefficients are. But here's the kicker -- it is actually pretty rare for two algorithms to truly have the same time complexity. If we look carefully enough, we usually discover that the dominant terms are slightly different. Where we really see this is when we are looking at new "better" algorithms that are competing with long-established and highly-optimized existing algorithms. As an example, you might look at the time complexity of the best algorithms for finding the integer factorization of a large number.

Now this is all from a theoretical standpoint where we talk about the behavior as the size of the problem grows arbitrarily large. But, in practice, someone implementing an algorithm usually has at least some idea of how big the problems are that their implementation will be called upon to solve. If execution time is even a concern, then they care about the behavior of their implementation of their chosen algorithm on the size of problems they need to apply it too. So here they often care about that coefficient out front and they may also care about some of the asymptotically non-dominant terms because they may well be dominant for smaller problems. It is frequently the case that "faster" algorithms have significant one-time set-up and wrap-up costs compared to "slower" algorithms and until the problem size gets large enough to amortize those one-time costs, the slower algorithm will actually outperform the faster algorithm.

AGain Again Again, thank you very much ! I've read ur post double times to be fully cleared on that point and understand gap !
lemme please describe something that I guess it's really the time to say; generally(not specifically to this post) whenever I have something theoretically in any materials for instance " T(n) " I start thinking how T(n) is compiled on something more reality (like must having analogues for understanding it) , I guess that way make me much harder to understand the materials, although when I really not thinking how that something "Theoretically" reacted on our lives I find it much easier and understand it better as something "Theoretically" and going like this , my question I'm a lil on confused how could I think "rightly" in proper way? I know everybody thinks different but I'm meaning may you could help me to boost my thinking on problems/materials in a manner to start thinking about the problem and now why "that definition like that" and only just how is that going ! ; I don't know if others suffer like what I'm suffering and straggling but yeah I don't care just want to get steps that boost me up towards!

In abbreviations, I'm always converting things to physically and that's make the understanding harder I "guess"

 

Out of curiosity, how long ago was it that you did this test?

Five to ten years ago. As I recall I sorted 10's of thousands of fairly long randomized strings. Naturally, the time to execute is related to the time to compare two objects being sorted.

 

Five to ten years ago. As I recall I sorted 10's of thousands of fairly long randomized strings. Naturally, the time to execute is related to the time to compare two objects being sorted.

I was wondering how much the time to compare objects influenced the results, but I would think that the average time to compare two strings is pretty small no matter how long they are since you only have to go to the first place in which they differ. But, having said that, as the list gets closer and closer to being sorted you are spending more time comparing strings that have pretty long common prefixes. Also, there's the time to perform the swaps, which if it's not done using references can take some time.

I was troubled because the ratio of your results was so markedly different than the ratio of mine, but I now see that the average time to do the comparisons is probably not constant time. But I'm not sure I buy that too much since, even with 100,000 strings, the likelihood that they are the same beyond the first four or five characters is getting pretty small.

 

I was wondering how much the time to compare objects influenced the results, but I would think that the average time to compare two strings is pretty small no matter how long they are since you only have to go to the first place in which they differ. But, having said that, as the list gets closer and closer to being sorted you are spending more time comparing strings that have pretty long common prefixes. Also, there's the time to perform the swaps, which if it's not done using references can take some time.

I was troubled because the ratio of your results was so markedly different than the ratio of mine, but I now see that the average time to do the comparisons is probably not constant time. But I'm not sure I buy that too much since, even with 100,000 strings, the likelihood that they are the same beyond the first four or five characters is getting pretty small.

I want to ask last question about that subject:
if I have upper bound of n/2 you said above because it's O(n) then we can assume it's like n/2, but also for example n/4 is O(n) why aren't we saying that upper bound of n/2 is like n/4? still frankly lil confused ..
to elaborate by an example if I have T(n)=T(upper.bound(n/2)) +C we said above it's like T(n)=T(n/2)+C and that's because n/2 and upper.bound(n/2) is o(n) but also n/4 for example is O(n) why we couldn't say it's like it?! like T(n)=T(n/4)+C ?! thanks !