programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

time complexity for this algorithm

Dan D'amico
Ranch Hand
Posts: 94
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 ?

Liutauras Vilda
Sheriff
Posts: 4922
334
Precise evaluation of the runtime is very difficult. In fact, it is not need.
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
• 1
Ologn² 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 logn² 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?

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

Dan D'amico
Ranch Hand
Posts: 94
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 of log²n, so I think squared has the higher precedence. Since logn² 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)

Liutauras Vilda
Sheriff
Posts: 4922
334
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

Liutauras Vilda
Sheriff
Posts: 4922
334
And got another theory!

Since we don't know the implementation of substring() method, does it mean we cannot evaluate "our" algorithm complexity?

Dan D'amico
Ranch Hand
Posts: 94
Liutauras Vilda wrote:And got another theory!

Since we don't know the implementation of substring() method, does it mean we cannot evaluate "our" algorithm complexity?

its O(n^2 * logn^2)

Campbell Ritchie
Marshal
Posts: 56562
172
Dan D'amico wrote: . . .its O(n^2 * logn^2)
There is no such thing. That is O(n²logn).

Dan D'amico
Ranch Hand
Posts: 94
Campbell Ritchie wrote:
Dan D'amico wrote: . . .its O(n^2 * logn^2)
There is no such thing. That is O(n²logn).

what about the nested for loops the outer is multiplied by 2 , and the inner for loop divided by 2 . so its logn * logn

Campbell Ritchie
Marshal
Posts: 56562
172
• 1
That would be log²n Or (logn)² Or log logn

Dan D'amico
Ranch Hand
Posts: 94
Campbell Ritchie wrote:That would be log²n Or (logn)² Or log logn

yes. thanks