5 years later and this is still valuable. It covers the essential parts, straight to the point and very clear. This is why I always look at underrated or much lengthy videos first for explanations than the ones with click-baits and super simplified explanations to cater short-term attention span of people.
(=) can be counted too! Infact, there are many operations in that line, c[i][j] = a[i][j]+b[i][j] 1. Array indexing: Accessing the element of an array like a[i][j] 2. Sum: a[i][j]+b[i][j] 3. Assignment : c[i][j] = a[i][j]+b[i][j] In the example above I considered only Sum, but you are free to consider any other operation as well. The best way would be to consider all three. Anyway, the time complexity does not change as frequency of basic operation is the same (n^2). k1*(n^2) = O(n^2) k2*(n^2) = O(n^2) k3*(n^2) = O(n^2)
on the second example. Addition takes 1 unit of time to be performed but what about storing the value that was taken. Doesn't that count as 1 unit of time as well? Adding+storing=2 units of time. Am i right or wrong?
Yes, you are right. It is always good to record the execution time of basic operation as a constant (say k) instead of recording as units (1,2 etc). This will avoid all confusions. For a different computer k can be different (like it may take less time for a powerful super computer to add than a desktop PC). If you record as 'k' all machine specific factors can be taken care of.
Yes frequency is crucial! Say there is a basic operation (k unit execution time) inside a for loop (say runs n time). Total time would be O(kn) = O(n) linear time. If you now remove the loop, total time now is O(k) which is constant time.In this case frequency is 1. This is how frequency contribute to the time complexity.
In the for loop i=1,not 0 because I have already assumed that element at index 0 as maximum. The basic operation is executed only when the condition of for loop become true. The condition of for loop (i
@@SunilDhimal Based on this introduction to Operation count method. One way to estimate the time complexity of a program or method is to select one or more operations, such as add, multiply, and compare, and to determine how many of each is done. The success of this method depends on our ability to identify the operations that contribute most to the time complexity. What would be a case in which we would select more than one basic operation? and How would you relate their time complexities.
@@Daniel-wt9bh : If we select more than one basic operation, the time complexity is more real. If we consider the contribution of all operations, then the method is called step count method. I have separate explanation for that: th-cam.com/video/53sC2ioHUM0/w-d-xo.html
5 years later and this is still valuable. It covers the essential parts, straight to the point and very clear. This is why I always look at underrated or much lengthy videos first for explanations than the ones with click-baits and super simplified explanations to cater short-term attention span of people.
I spent 8 hours looking for a good explanation but finally ....
Sir, Thank You For making such helpful and conceptual videos. Kindly Upload videos on divide and conquer! Much awaited
Nice explanation
Great explanation!
Amazing video. Thank you.
Thank you for the video!
thank you💌❤🤍
Doesn’t = count as one operation for the matrices basic operation?
(=) can be counted too! Infact, there are many operations in that line, c[i][j] = a[i][j]+b[i][j]
1. Array indexing: Accessing the element of an array like a[i][j]
2. Sum: a[i][j]+b[i][j]
3. Assignment : c[i][j] = a[i][j]+b[i][j]
In the example above I considered only Sum, but you are free to consider any other operation as well. The best way would be to consider all three. Anyway, the time complexity does not change as frequency of basic operation is the same (n^2).
k1*(n^2) = O(n^2)
k2*(n^2) = O(n^2)
k3*(n^2) = O(n^2)
Sir,when is next video coming up.. Totally relied on it
In first example..Why have we not taken increment and assigning value to variable as operation?
on the second example.
Addition takes 1 unit of time to be performed but what about storing the value that was taken. Doesn't that count as 1 unit of time as well? Adding+storing=2 units of time. Am i right or wrong?
Yes, you are right. It is always good to record the execution time of basic operation as a constant (say k) instead of recording as units (1,2 etc). This will avoid all confusions. For a different computer k can be different (like it may take less time for a powerful super computer to add than a desktop PC). If you record as 'k' all machine specific factors can be taken care of.
@@SunilDhimal thank you.
So you are saying that the important part is always the frequency and not the exact execution time for each operation?
Yes frequency is crucial!
Say there is a basic operation (k unit execution time) inside a for loop (say runs n time). Total time would be O(kn) = O(n) linear time.
If you now remove the loop, total time now is O(k) which is constant time.In this case frequency is 1.
This is how frequency contribute to the time complexity.
@@SunilDhimal Thank you, I really appreciate it
whattt i just got it thankss
Thanks.
Wouldn't it be i = 0 in the for loop instead of i = 1 for C(n) to be n - 1? First example.
In the for loop i=1,not 0 because I have already assumed that element at index 0 as maximum. The basic operation is executed only when the condition of for loop become true. The condition of for loop (i
@@SunilDhimal I see max = a[0];
Thank you.
@@SunilDhimal Based on this introduction to Operation count method.
One way to estimate the time complexity of a program or method is to select one or more
operations, such as add, multiply, and compare, and to determine how many of each is
done. The success of this method depends on our ability to identify the operations that
contribute most to the time complexity.
What would be a case in which we would select more than one basic operation? and How would you relate their time complexities.
@@Daniel-wt9bh : If we select more than one basic operation, the time complexity is more real. If we consider the contribution of all operations, then the method is called step count method. I have separate explanation for that: th-cam.com/video/53sC2ioHUM0/w-d-xo.html