0

My toString() method's time complexity is supposed to be O(Row*Col). What I can see from the code is that there are two for-loops where one of them is running through the rows and the other one is running through the cols.

Does the declaration of String variables take a lot of time? I have written code but does it have that exact time complexity?

Improve this question
5
  • :) :) :) :) @TAsk, is there any way to shorten it ?? Can StringBuilder usage shorten it?? Commented Sep 8, 2015 at 5:29
  • 1
    First of all, get rid of all the redundancy, like a switch with only one case. Commented Sep 8, 2015 at 5:31
  • @John That looks like the printing of a board (seen a lot of board questions on here lately). You don't build a string of the entire board in a toString() method. Create a method called printBoard() instead. toString() is for returning a string representation of the object, e.g. for debugging, so a return value of "board(10 x 15)" would be appropriate. Commented Sep 8, 2015 at 5:33
  • You could probably also gain a lot by using String.format Commented Sep 8, 2015 at 5:33
  • use something like secondLine1 += "|" + " ".subString(0," ".length() - temp.length()) + temp;. String.format is quite slow. Externalize this string " " Commented Sep 8, 2015 at 5:46

1 Answer 1

Reset to default
1

Yes, the complexity is O(Row*Col) or O(N) with N being the number of elements.

Declarations do not enter into the asymptotic running time, because these have constant time.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

So, the toString() does have tha O(R*C) complexity, right? @popovitsj
Btw, @popovitsj, isnt O(RC) equivalent to O(N^2) ? I have the nested loop in the code, isnt the time complexity O(N^2) or O(RC) ?
@John, it's equivalent to O(N^2) if R == C. It's often forgotten, but if you say a running time is O(N-something), you should always state what N stands for. In this case I would call this algorithm O(N) with N being the number of elements, and the number of elements can of course be calculated with R*C

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.