Q: In the graph why `Θ(n)` is not linear? the time taken for an increment in the for loop will be a constant always or will it be varying? and in the second graph why `k1` and `k2` are not constant? why it is curved? is `Θ(n) = c1⋅n+c2`

That's not a graph of Θ(n), it's a graph of the running time. Θ(n) represents the upper and lower bound on the running time.

Q: Ok I have a question, if for example I have (n+1)n/2 and im trying to prove that is not a set of Theta(n), but I am a bit confused, so say for example k1,k2 and N, does k1 always have to be 1 or can it be greater than one, say 2, and k1=2, k2=4 and N = 1 : then by doing 2*2 <= (2+1)2/2 <=4*2, which is equivalent to 4 <= 3 <= 8, by my understanding this would prove it false but, as you may knowI am still confused and would like to know if the constant k1 always have to be 1 or can it be greater?

Now im even more confused, what do you mean divide everything by n? Give me an example please

Q: In the first paragraph, why is "possibly return the value of guess" included in the list of things that happens each time the for loop iterates? Shouldn't it be included in c2 instead because it only happens once?

The reason why this is included in c1 rather than c2 is a little surprising. While returning the value of the guess occurs at most once, _not returning the value of the guess occurs each time the loop iterates_. An "if" statement must skip past the code that will not be run when the condition is false, and the jump over the code that won't happen is what takes up this small, but very real, amount of time each iteration.

Question 1

I was confused about where k1 and k2 came from, as well as tight bound. I read this StackOverflow answer and it gave me a bit more to go on: http://stackoverflow.com/a/471292/17188 -- anyone else have a better explanation/clarification?

Accepted Answer

k1 and k2 are simply real numbers that could be anything as long as f(n) is between k1*f(n) and k2*f(n).

Let's say that doLinearSearch(array, targetValue) runs at f(n)=2n+3 speed in microseconds on a certain computer (where n is the length of the array) and we're trying to prove that it has Θ(n) time complexity. We would need to find two real numbers k1, k2, and n0 such that k1*n<2n+3<k2*n for all n>n0. We need to solve for k1, k2, and n0. It happens that there are infinitely many solutions, but we only need to find one to complete our proof.

Now, it happens that the solution k1=1, k2=3, and n0=4 works. This means 1*n<2n+3<3n for all n>4. For example:
1*5<2*5+3<3*5 --> 5<13<15
1*6<2*6+3<3*6 --> 6<15<18
1*7<2*7+3<3*7 --> 7<17<21
1*4.1<2*4.1+3<3*4.1 --> 4.1<11.2<12.3
In mathematics, these examples alone wouldn't actually suffice for a proof, but there is a rigorous way to prove that this inequality is true. It's just rather complicated.

You might ask why I didn't pick n0=3 instead. After all, that seems to be the minimal possible answer, because 3 doesn't work (1*3<2*3+3<3*3 --> 3<9<9), but all n>3 works. However, while that's true, I don't need the minimal possible n0. I just need any n0 that works. If I find one solution, then I've proved what I've needed to.

I would imagine if you were taking a college level computer science course, you might need need to prove Big-Θ, Big-O, and Big-Ω statements. Also, the make-up of the actual function would probably be determined by something else because you don't usually work with actual microseconds or milliseconds in general time complexity. For example, maybe the algorithm has two loops that go from 0 to n (where n is the input of the algorithm), in which case the function might be f(n)=2n. In general, you won't need to rigorously prove any complexity theory statements because as I said before, it's rather complicated (although won't be if you have experience proving limits). Instead, you can just keep the rule of thumb for polynomials that you can drop all of the terms except the one with the highest exponent, and then drop the exponent.

I hope this helps!

Question 2

What exactly does asymptotic mean? In maths at school I learned that an asymptote is a line that a curve never touches but the distance between them approaches zero. However, that definition isn't really helping me to understand this concept.

Accepted Answer

When we are talking about "asymptotic" behavior here, we are talking about the behavior of  functions when n is very large (approaching infinity).

We have 3 curves that we worry about.
A curve for the running time function f(n). (we often don't know exactly what this function looks like)
A curve that we know is "above" the running time function when n is large.  ( Big-O )
A curve that we know is "below" the running time function when n is large.  (Big-Omega)
(Note: the terms "above" and "below" aren't entirely accurate here, and Big-O and Big-Omega actually describe a set of curves rather than just one curve)

If we can squeeze the curves that are  "above" and "below" the running time function close enough, then we can figure out  Big-Theta. This is useful when we don't know exactly what the running time curve looks like, which is most often the case, because Big-Theta is just a "scaled" version of the running time curve (it can tell us the shape of the curve).
(Note: this isn't entirely accurate,  it only scales the highest order behavior of f(n)  (the parts that dominate as n increases) , and Big-Theta is also a set of curves)

Hope this makes sense

Question 3

I am just wondering what level is this course, I am 15 and it seems to be sorta confusing. I am trying hard to understand the Big-Theta notation, but it seems to get confusing rather quickly. I might just be confusing things in my head, not sure. I am going to continue working on this, but I would like to know what level this course is. Thanks

Accepted Answer

It is difficult to give a grade level to this type of material since when and how it is taught varies so widely. Personally, I think it leans towards college level, especially the asymptotic notation calculations. It is important to know what types of things will slow your programs to the point of frustration. For the amateur coder, it is not so important to calculate and graph it! I don't think most software engineers approach issues that way, unless they need to pitch a project or they are really stuck on a difficult bottleneck.
People who are more recently in CS may disagree (I moved over to math), but I think the much more interesting aspects of algorithm study involve problem solving and translating solutions into code. And until you do a bunch of that, measuring how fast your subroutine goes won't be of much help.
Anyway, hope this is useful and you enjoy whichever areas you end up focusing on.

Question 4

So it seems to me that Big O is the worst case scenario, Big Theta is the range of cases from best to worst and Big Omega I haven't got to yet. ...now why couldn't you guys just say that?

Accepted Answer

They didn't say that, because it would be incorrect.
Big O, Big Theta and Big Omega are often all used to measure the worst case scenario (this is most often the case).
They could also all be used to measure an average case (this happens often).
They could also all be used to measure the best case (we rarely care about best cases)
The measurements of Big-O, Big-Theta, and Big-Omega would often be different depending on which case was picked.

Here's the simple version of what Big-O, Big-Theta, and Big-Omega are :
If you have a function f(N):
Big-O tells you which functions grow at a rate >= than f(N), for large N
Big-Theta tells you which functions grow at the same rate as f(N), for large N
Big-Omega tells you which functions grow at a rate <= than f(N), for large N
(Note: >= , "the same", and <= are not really accurate here, but the concepts we use in asymptotic notation are similar):

We often call Big-O an upper bound, Big-Omega a lower bound, and Big-Theta a tight bound. Often in computer science the function we are concerned with is the running time of an algorithm for inputs of size N.

Hope this makes sense

Question 5

Where I can find a good reading about how to compute the complexity of an algorithm? I want to understand how to figure out if an algorithm if n.log.n, n^2, etc.

Accepted Answer

Here's the quick version of how to analyze running times:
(I use n below for the problem size )

-Replace any simple block of operations that are performed without calling a function with a constant
 e.g. 
```
x = 5* 4 + 2; 
y++;
z = x * y;
``` 
will run in some constant amount of time
we usually label that time with some variable e.g. 'c1'

-If you have a for loop that loops n times, the running time is about n times the running time of the code inside the loop (this neglects the constant amount of time to initialize the for loop and the constant amount of time every loop to perform the comparison and increment)
e.g. 
```
for(var i=0; i < n ; i++){
	x = 5* 4 + 2; 
	y++;
	z = x * y;
}
``` 
we determined above that the code inside of the for loop runs in 'c1'
so the running time of this code is about 'c1 * n'

e.g.
```
for(var j=0; j < n; j++){
	for(var i=0; i < n ; i++){
		x = 5* 4 + 2; 
		y++;
		z = x * y;
	}
}
``` 
we determined above that the code inside of our outermost for loop runs in about 'c1 * n'
so this code runs in  about 'c1 * n * n' or 'c1 * n^2'

-If after each iteration of an algorithm the problem is '1/a' of the size before the iteration then the code will iterate about 'log_a(n)' times.  Thus, the running time of the code will be about log_a(n) times the running time of the code run each iteration.
e.g.
```
while( n>1 ){
	x = 5* 4 + 2; 
	y++;
	z = x * y;

n = n/2;
}
```
the code inside of the while loop runs in some constant time 'c2'
the size of the problem size n, is reduce in 1/2 each iteration
so this code iterates about 'log_2(n)' times
so the running time of the code is about 'c2 * log_2(n)'

Beyond the above, I would look at the analysis in the articles here, and study how they find the running times to learn other techniques on how to figure out the running times of algorithms.

"Discrete Mathematics with Applications" by Susanna Epp, discusses how to analyze running times in the chapter on Efficiency of Algorithms.

Hope this makes sense

Question 6

I'm still not clear about what "tightly bound 
" means in this context. I do, however understand everything else, including the definition of "Asymptotic".

Accepted Answer

The upper bound tells us what grows asymptotically faster than or at the same rate as our function. The lower bound tells us what asymptotically grows slower than or at the same rate as our function. Our function must lie somewhere in between the upper and lower bound.

Suppose that we can squeeze the  lower bound and our upper bound closer and closer together. Eventually they will both be  at the same asymptotic growth rate as our function. That's what we would call tight bounds (where the upper bound and lower bound have the same growth rate as the function).

Question 7

I did not understand what you meant  when you spoke about the constants k1 and k2; can you please elaborate some more?

Accepted Answer

Suppose you have two functions, f(n) and g(n).
If,for large values of n, you are able to:  
-squeeze f(n) between  k1 * g(n) and k2 * g(n)   
Then:
-you can say f(n) is Θ( g(n) )

You are allowed to pick any value you want for k1 and k2 as long as they are both greater than zero.

e.g. 
Suppose: f(n) = 6n + 5 and  g(n) = n + 2
We could pick k1 = 1 and k2 = 6 and n >= 1

We can see that: k1 * g(n) <= f(n) <= k2 * g(n) 
because: 1 *(n+2) <= 6n+5 <= 6*(n+2)

We successfully squeezed  f(n) between  k1 * g(n) and k2 * g(n)  so we can say:
f(n) is Θ( g(n))

Hope this makes sense

Question 8

In the graph why `Θ(n)` is not linear? the time taken for an increment in the for loop will be a constant always or will it be varying? and in the second graph why `k1` and `k2` are not constant? why it is curved?

is `Θ(n) = c1​​⋅n+c​2`
​​

Accepted Answer

That's not a graph of  Θ(n), it's a graph of the running time.  Θ(n) represents the upper and lower bound on the running time.

Question 9

Ok I have a question, if for example I have (n+1)n/2 and im trying to prove that is not a set of Theta(n), but I am a bit confused, so say for example k1,k2 and N, does k1 always have to be 1 or can it be greater than one, say 2, and k1=2, k2=4 and N = 1 : then by doing 2*2 <= (2+1)2/2 <=4*2, which is equivalent to 4 <= 3 <= 8, by my understanding this would prove it false but, as you may knowI am still confused and would like to know if the constant k1 always have to be 1 or can it be greater?

Accepted Answer

Now im even more confused, what do you mean divide everything by n? Give me an example please

Question 10

In the first paragraph, why is "possibly return the value of guess" included in the list of things that happens each time the for loop iterates? Shouldn't it be included in c2 instead because it only happens once?

Accepted Answer

The reason why this is included in c1 rather than c2 is a little surprising. While returning the value of the guess occurs at most once, _not returning the value of the guess occurs each time the loop iterates_. An "if" statement must skip past the code that will not be run when the condition is false, and the jump over the code that won't happen is what takes up this small, but very real, amount of time each iteration.

Course: Computer science theory > Unit 1

Big-θ (Big-Theta) notation

Want to join the conversation?