Hi guys, I want to verify why when I have 1+2+3+4+5+...+n I can't write like this Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)... = n*Θ (1) ?! we already know that any constant can be converted to Θ (1) !

another question, if i=4 till i<16 {i=i*4} then it will make 4 iterations because 4*4=16 but why if i=16 i>4{i=i/4} then it's the same number of iterations? it doesn't make a sense for me..any help please?

Another issue, lets suppose given T(n)=T(n/4)+C , why it's wrong to say like this:
T(n)=T(n/4)+c=T((1/2)*n/2) +c= T(n/2)+c (neglecting the constant (1/2) because O(n/4)=O((1/2)*n/2)=O(n/2) so (1/2) is absorbed by O() )?

thanks for helpers

 

Any help guys? thanks.

 

Hi guys, I want to verify why when I have 1+2+3+4+5+...+n I can't write like this Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)... = n*Θ (1) ?! we already know that any constant can be converted to Θ (1) !

I don't understand the question, can you rephrase it? What is the series 1 + 2 + 3 + ... + n supposed to represent?

another question, if i=4 till i<16 {i=i*4} then it will make 4 iterations because 4*4=16 but why if i=16 i>4{i=i/4} then it's the same number of iterations? it doesn't make a sense for me..any help please?

Your programmatic logic seems wrong, as each loop will have one iteration. In the first, after one iteration 4 * 4 = 16, which is not less than 16, so the loop stops. A similar thing happens in the second loop.

As a beginner, it's a good idea to actually write, compile, and execute your programmatic ideas to make sure you're saying what you think you're saying. As you get more experience, you'll be able to write what you think without as much testing.

Another issue, lets suppose given T(n)=T(n/4)+C , why it's wrong to say like this:
T(n)=T(n/4)+c=T((1/2)*n/2) +c= T(n/2)+c (neglecting the constant (1/2) because O(n/4)=O((1/2)*n/2)=O(n/2) so (1/2) is absorbed by O() )?

What does T() represent? As for O(n/4), in terms of asymptotic behavior, I'd call it linear in n: O(n/4) = O(1/4 * n) ≅ O(n).

 

I don't understand the question, can you rephrase it? What is the series 1 + 2 + 3 + ... + n supposed to represent?

it's a sum of numbers ..doesn't matter exactly what it's ..

Your programmatic logic seems wrong, as each loop will have one iteration. In the first, after one iteration 4 * 4 = 16, which is not less than 16, so the loop stops. A similar thing happens in the second loop.

my question is why similar things happen?! why it's actually when I say i=i*4 and i=i/4 isn't the same at all .. so how iterations are the same?!

As a beginner, it's a good idea to actually write, compile, and execute your programmatic ideas to make sure you're saying what you think you're saying. As you get more experience, you'll be able to write what you think without as much testing.

alright.

What does T() represent? As for O(n/4), in terms of asymptotic behavior, I'd call it linear in n: O(n/4) = O(1/4 * n) ≅ O(n).

yes exactly but I'm saying if O(n/4) in terms of asymptotic it's the same to say O((1/2)*n/2)=O(n/2) so why we cant write instead of "T(n)=T(n/4)+c " that equation "T(n)=T(n/2) +c " ? because 1/2 is already absorbed by O() so O(n/4)=O((1/2)*n/2) and 1/2 I can neglect it ..cant?!

 

Hi guys, I want to verify why when I have 1+2+3+4+5+...+n I can't write like this Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)+Θ (1)... = n*Θ (1) ?! we already know that any constant can be converted to Θ (1) !

You seem to be confusing very different concepts.

If you are trying to find the time complexity of computing the sum of the first n natural numbers, then what you say is correct provided you realize that your aren't replacing the constants with Θ (1) but rather claiming that computing the next term is done in constant time, for instance by adding one to the prior term.

another question, if i=4 till i<16 {i=i*4} then it will make 4 iterations because 4*4=16

Why four iterations. In the first iteration i = 4. Then you multiply this by 4 to get 16 and since 16 is NOT less than 16, there is no second iteration.

but why if i=16 i>4{i=i/4} then it's the same number of iterations? it doesn't make a sense for me..any help please?

What is there to make sense of?

Another issue, lets suppose given T(n)=T(n/4)+C , why it's wrong to say like this:
T(n)=T(n/4)+c=T((1/2)*n/2) +c= T(n/2)+c (neglecting the constant (1/2) because O(n/4)=O((1/2)*n/2)=O(n/2) so (1/2) is absorbed by O() )?

T(n) is the ACTUAL amount of time (or clock cycles, or whatever) required to solve the worst-case problem of size n.

So

T1(n) = 5n

is NOT equal to

T2(n) = 6n

For n = 10, the first is 50 and the second is 60. Not the same.

If you find the time complexity class of these, then they are both linear time complexity and, as the size of the problem grows arbitrarily large, the ratio of the two becomes, at most, a constant.

 

it's a sum of numbers ..doesn't matter exactly what it's ..

If we take it as given that a single addition takes constant time -- in other words, if we're focusing on the series sum algorithm rather than the implementation details of addition -- then n additions has O(n) complexity.

A much better algorithm for that series would use Gauss's n(n + 1) / 2 formula, which has O(1) complexity. Note that we're talking specifically about the complexity of the series sum algorithm, i.e., how the algorithm itself -- only the algorithm, not any lower-level implementation details -- behaves with respect to its input. A potential source of confusion arises when we instead consider the algorithmic behavior of the addition operation versus the multiplication operation, i.e., how addition and multiplication are actually implemented. Using the standard algorithms from elementary school, adding two n-bit numbers has O(n) complexity, while multiplying two n-bit numbers has O(n^2) complexity.

Why is the multiplication in the n(n + 1) / 2 formula considered O(1), while multiplication itself is O(n^2)? Because in the series sum algorithm, the n(n + 1) / 2 formula executes the same number of times (once), regardless of the value of n. Note that the n in O(n^2) refers to the size of the input (in this case, the number of bits to be multiplied), while the n in n(n + 1) / 2 is just a single number, an entirely different thing.

Suppose that we give the n(n + 1) / 2 formula a number that is m-bits wide. To find the result using the standard multiplication algorithm, the formula will require on the order of m^2 steps. So, to characterize the total runtime performance of n(n + 1) / 2 including all of its individual multiplications, we might say that T(n) = k + O(m^2) ≈ k + O( (log n)^2 ), where k is a constant that captures the specific O(1) performance, and m ≈ log2(n + 1) is the number of bits in the decimal number n.

my question is why similar things happen?! why it's actually when I say i=i*4 and i=i/4 isn't the same at all .. so how iterations are the same?!

Because you've reversed the loop logic in the second case. Counting forward from 1 to 10 takes the same number of steps as counting backward from 10 to 1.