in matlab coding how to write Big-O notation

Question

lokireddy sarala 2018-1-9

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/376244-in-matlab-coding-how-to-write-big-o-notation

回答： lokireddy sarala 2018-3-17

采纳的回答： Walter Roberson

e=O(log(n))

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Walter Roberson 2018-1-9

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/376244-in-matlab-coding-how-to-write-big-o-notation#answer_299280

MATLAB in general has no concept of Big-O notation, and cannot compute it or use it.

The closest that MATLAB gets to this is that inside the MuPAD symbolic engine, series are represented with an order term, such as

1 + x + x^2/2 + x^3/6 + x^4/24 + x^5/120 + O(x^6)

This is related to big-O notation in that both have to do with order approximations, but the symbolic engine use does not have to do with code complexity in either time or space.

5 个评论
显示 3更早的评论隐藏 3更早的评论

Walter Roberson 2018-1-23

Is lamda(1-t) a function call? Is it a scalar multiplication? Is it an algebraic matrix multiplication? Is it element-by-element multiplication ?

In big-O notation, lamda and t would be assumed to be non-negative integers.

if lamda = 0 then lamda(1-t) is 0*something = 0 and then you would have log(0) + log(log(0)) + O(1/sqrt(log(0))) + O(log(log(0))) = infinity + log(infinity) + O(1/sqrt(infinity) + O(log(infinity)) = infinity + infinity + O(1/infinity) + O(infinity) = infinity + O(0) + O(infinity) = infinity + O(infinity)
if lamda = 1 and t = 0 then lamda(1-t) is 1*1 but lamda*t = 0, so you would have log(lamda*0) + log(log(lamda)) + O(1/sqrt(log(lamda)) + O(log(log(lamda)) = infinity + log(0) + O(1/sqrt(0)) + O(log(0)) = infinity + infinity + O(infinity) + O(infinity) = infinity + O(infinity)
if lamda = 1 and t = 1 then lamda(1-t) is 1*0 and lamda*t = 1, so you would have log(1) + log(log(0)) + O(1/sqrt(log(0)) + O(log(log(1)) = 0 + log(infinity) + O(1/sqrt(infinity)) + O(log(0)) = infinity + O(0) + O(infinity) = infinity + O(infinity)
if lamda > 0 and t > 1 then lamda(1-t) is lamda(a negative number) which would be negative, and log() of that would become complex

I would need to work through all of the cases to be sure, but it looks to me as if your results are always going to be infinite or complex.

... Unless, that is, you using big-O notation to mean something different than it does in computer science. https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Walter Roberson 2018-2-1

When lamda is 2 or more and t is > 1, then your formula gives a complex result.

"but i need code for Big-O and Small o notations in matlab."

There is no code for that. They are theoretical analysis, not something that can be easily computed.

Walter Roberson 2018-2-1

I see from https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations that in Small-O notation, o(g(n)) means "f is dominated by g asymptotically" and that there is a formal limit involved, lim n->0 f(n)/g(n) = 0.

In order prove such a thing in MATLAB, you would need to have the formula f(n) and g(n), and you would need to use the symbolic toolbox to take limit(f(n)/g(n), n, inf) and show that it was 0. This is not always practical to do by the symbolic toolbox but it does work sometimes. But proving that g(n) is the "smallest" function with this property requires mathematical analysis that is difficult to impossible to do through symbolic computations.

请先登录，再进行评论。