Dan D'amico

Ranch Hand

Posts: 94

posted 2 years ago

this is silly algorithm that just want to check knowledge. its actually easy one and i just want to make sure that my answer is valid.

method 1 is O(logn^2)

method 2 is O(n^2) * O(logn^2) is this a valid answer ? because n^2 is much bigger then logn^2 and maybe i only need to put n^2 as the wrost case.

if method1 was just one for loop and the time complexity was logn.

then the complexity of method2 was n^2 * logn but the wrost case would be just n^2 because in avery large n the logn method doesnt matter that much. am i correct ?

method 1 is O(logn^2)

method 2 is O(n^2) * O(logn^2) is this a valid answer ? because n^2 is much bigger then logn^2 and maybe i only need to put n^2 as the wrost case.

if method1 was just one for loop and the time complexity was logn.

then the complexity of method2 was n^2 * logn but the wrost case would be just n^2 because in avery large n the logn method doesnt matter that much. am i correct ?

posted 2 years ago

Precise evaluation of the runtime is very difficult. In fact, it is not need.

All needed is to estimate the behavior of the program on large inputs (worst case).

So, O(logn^2) is irrelevant. As you mentioned yourself it is enough to say that is O(n^2). Which is correct.

All needed is to estimate the behavior of the program on large inputs (worst case).

Dan D'amico wrote:method 2 is O(n^2) * O(logn^2)

So, O(logn^2) is irrelevant. As you mentioned yourself it is enough to say that is O(n^2). Which is correct.

Campbell Ritchie

Marshal

Posts: 56562

172

posted 2 years ago

- 1

O

Do you really mean * or do you mean +?

If method1 runs in n

I am not sure myself, but I think I would like some more explanation.

*log*n² complexity? Which operator has the higher precedence, squared or log? If log has a higher precedence, then you have a sort of*log*²n, so I think squared has the higher precedence. Since*log*n² is 2*log*n, your O*log*n² complexity reduces to O*log*n complexity.Do you really mean * or do you mean +?

If method1 runs in n

*log*n time and it is called by method2 and the compiler doesn't notice the missing argument (), where do you get logarithmic time from? Doesn't method1 run in On*log*n time? And if method2 runs in quadratic time, why doesn't the whole program run in On³*log*n time?I am not sure myself, but I think I would like some more explanation.

Dan D'amico

Ranch Hand

Posts: 94

posted 2 years ago

method1 time complexity is logn^2 since the outer loop iterate the input by multiplicity of 2 each interation O(logn)

and the inner for loop is divided by 2 each iteration O(logn) so totall O(logn * logn) = O(logn^2)

method2 - outer for loop is O(n) , inner for loop is O(n) the call for method 1 inside the inner loop is O(logn^2)

so O(n * n) * O(logn^2) = O(n^2 )* O(logn^2)

Campbell Ritchie wrote:Ologn² complexity? Which operator has the higher precedence, squared or log? If log has a higher precedence, then you have a sort oflog²n, so I think squared has the higher precedence. Sincelogn² is 2logn, your Ologn² complexity reduces to Ologn complexity.

Do you really mean * or do you mean +?

If method1 runs in nlogn time and it is called by method2 and the compiler doesn't notice the missing argument (), where do you get logarithmic time from? Doesn't method1 run in Onlogn time? And if method2 runs in quadratic time, why doesn't the whole program run in On³logn time?

its * O(n^2) * O(logn^2)

I am not sure myself, but I think I would like some more explanation.

method1 time complexity is logn^2 since the outer loop iterate the input by multiplicity of 2 each interation O(logn)

and the inner for loop is divided by 2 each iteration O(logn) so totall O(logn * logn) = O(logn^2)

method2 - outer for loop is O(n) , inner for loop is O(n) the call for method 1 inside the inner loop is O(logn^2)

so O(n * n) * O(logn^2) = O(n^2 )* O(logn^2)

posted 2 years ago

Ok, I got Ritchie's point. Didn't notice that method2 calling method1.

So it can change game rules. I'm not sure now, needs to be double checked with some literature is encapsulated method in this case does counts to a total complexity.

Well, thinking from one perspective it should. Might someone else will know exactly.

One thing started make sense

Campbell Ritchie wrote:Doesn't method1 run in Onlogn time? And if method2 runs in quadratic time, why doesn't the whole program run in On³logn time?

Ok, I got Ritchie's point. Didn't notice that method2 calling method1.

So it can change game rules. I'm not sure now, needs to be double checked with some literature is encapsulated method in this case does counts to a total complexity.

Well, thinking from one perspective it should. Might someone else will know exactly.

One thing started make sense

Dan D'amico wrote:this is silly algorithm

Dan D'amico

Ranch Hand

Posts: 94

Campbell Ritchie

Marshal

Posts: 56562

172

Dan D'amico

Ranch Hand

Posts: 94

Campbell Ritchie

Marshal

Posts: 56562

172