4 ms·

Knowing the time complexity a given function you write is generally not important. However, the skill to analyze the complexity is an important one to have, bec

Knowing the time complexity a given function you write is generally not important. However, the skill to analyze the complexity is an important one to have, because when performance issues to come up, it is often a very powerful tool to have.

boyter 14y ago
Agreed. However it would probably be better to show someone some code with a loop in a loop and ask them why it could potentially be a problem. If they can tell you in Big O notation why its bad for large inputs then great, but so long as they can tell you why that's what really matters.
- jtheory 14y ago
  Right -- Big O notation is a useful formalization of a thinking process that in practice usually includes more information. That is -- anytime you write a loop, you'd better think about what's inside it (and how long those things will take), and -- given the amount of data you might be sending through that loop -- if that's a problem or not. I want someone to notice that they're making a remote call in a loop when it could be batched, cached, etc.. I don't want them to spend 2 days optimizing an algorithm tinkering with a bit of text that yes, is inefficient, but in practice is only going to take a few milliseconds anyway and isn't a hotspot.
doktrin 14y ago
My read was that he froze during the interview. Perhaps I was injecting my own experience, which once very literally went like this : interviewer : "what's the time complexity of blah" me : "hmm... O(1)" interviewer : "what's the space complexity?" me : "fuck, oh, I don't know" interviewer : "well, think about it. no stress" me (2 seconds later) : "oh, right, yeah, O(n)... of course" Not saying I'm proud of not taking the time to think a problem through, but sometimes people act really weird when under the gun.
- pacaro 14y ago
  I'm drawn to this for several reasons... Trite though it is, admitting that you don't know truly is on the path to wisdom. Not taking time to think things through is endemic in the workplace, not just an interview quirk. in the real world, many O(N) algorithms are in fact O(I don't know) because of unexpected or unpredicted behavior from language, compiler, interpreter, runtime, os, etc.

boyter 14y ago

Agreed. However it would probably be better to show someone some code with a loop in a loop and ask them why it could potentially be a problem. If they can tell you in Big O notation why its bad for large inputs then great, but so long as they can tell you why that's what really matters.

jtheory 14y ago
Right -- Big O notation is a useful formalization of a thinking process that in practice usually includes more information. That is -- anytime you write a loop, you'd better think about what's inside it (and how long those things will take), and -- given the amount of data you might be sending through that loop -- if that's a problem or not. I want someone to notice that they're making a remote call in a loop when it could be batched, cached, etc.. I don't want them to spend 2 days optimizing an algorithm tinkering with a bit of text that yes, is inefficient, but in practice is only going to take a few milliseconds anyway and isn't a hotspot.

doktrin 14y ago

My read was that he froze during the interview. Perhaps I was injecting my own experience, which once very literally went like this : interviewer : "what's the time complexity of blah" me : "hmm... O(1)" interviewer : "what's the space complexity?" me : "fuck, oh, I don't know" interviewer : "well, think about it. no stress" me (2 seconds later) : "oh, right, yeah, O(n)... of course" Not saying I'm proud of not taking the time to think a problem through, but sometimes people act really weird when under the gun.

pacaro 14y ago
I'm drawn to this for several reasons... Trite though it is, admitting that you don't know truly is on the path to wisdom. Not taking time to think things through is endemic in the workplace, not just an interview quirk. in the real world, many O(N) algorithms are in fact O(I don't know) because of unexpected or unpredicted behavior from language, compiler, interpreter, runtime, os, etc.