• Post Reply Bookmark Topic Watch Topic
  • New Topic

time complexity for this algorithm  RSS feed

 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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).
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
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That would be log²n Or (logn)² Or log logn
 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:That would be log²n Or (logn)² Or log logn

yes. thanks
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!