Hm. I just got introduced to it so we havent touched anything that is related to "unbound" or what so ever. We are just beginning the basic which is to identify what is the big o notation of a given block of code.
What I understood so far is that there are 2 types of complexity, addition and multiplication. It has been clarified that the 2nd block has a complexity of multiplication.
Also what I understood is to drop the lower order term and constant.
To be honest, the Big O Notation that I came up with for the 2nd block is based on observation. This is how I derived my answer for the 2nd block.
The answer for 2nd block is based on the observation of the following from my lecture notes.
Oh no, no, no. The "unbound variable n" was just a joke. It's because you didn't declare any variable called 'n', when you used it in your for loop. It'll return an error, saying that it couldn't find the value for that variable called 'n'.
You're right to say that the 2nd block has a "complexity of multiplication", if you want to call it that. I would normally just describe in a more.. err... "layman" way. Lol.
Yes. Do drop lower order terms and constants.
-------------------
Now, I think it is kind of clear where your issue lies.
For starters, you cannot assign
with any big O notation without understanding how many times the loop is carried out. A while/for loop doesn't necessarily have O
run time complexity. Instead, the run time complexity of any loop is determined by how many times the loop has to run.
Here's an easy example:
Code:
int k = 3;
while (k > 0) {
System.out.println("How many lines have I printed?");
}
If you take a closer look, you would easily recognise this to be an infinite loop. The program never terminates. It has a "run time complexity" of O(Infinity). The value of k does not affect the run time complexity of this algorithm in any particular way. This shows that you cannot immediately say a while/for loop has a run time complexity of O
carelessly.
Next, we have the most commonly seen example:
Code:
int k = 0;
int n = 5;
while (k < n) {
System.out.println("This is line number: " + k);
k = k + 1;
}
This is
completely equivalent (for most intent and purposes) to:
Code:
int n = 5;
for (int k = 0; k < n; k++) {
System.out.println("This is line number: " + k);
}
In both cases, the run time complexity is determined by the value of the variable 'n'. It has a linear relationship. If n is 5, the loop runs 5 times. If n is 20, the loop runs 20 times. We say that it has a run time complexity of O
.
Finally, here's the part where you are somewhat confused about. We have:
Code:
int n = 5;
while (n > 0) {
System.out.println("I am a line!");
n = n / 2;
}
We can always rewrite this as:
Code:
for (int n = 5; n > 0; n = n/2) {
System.out.println("I am a line!");
}
For both the while and for loop, in this case, their run time complexity is O(logn).
The characteristics of a O(logn) run time complexity, is one where you need to square the value of n, to double the number of operations done. This makes use of the mathematical derivation:
Code:
x = log(n)
2x = 2log(n) = log(n^2)
Here's a little demonstration to prove it. With the while loop:
Code:
while (k > 0) {
System.out.println("OP");
k = k / 2;
}
We run this with k = 7. We get:
Code:
OP // k = 7/2; here
OP // k = 3/2; here
OP // k = 1/2; here
We square the value of k, such that k = 49. We get:
Code:
OP // k = 49/2; here
OP // k = 24/2; here
OP // k = 12/2; here
OP // k = 6/2; here
OP // k = 3/2; here
OP // k = 1/2; here
Hence, this demonstrates the relationship between the value of n, and the number of loop operations executed, for a O(logn) run time complexity.
