What's the relationship between time complexity and runtime?

Question

I'm currently usng leetcode to prepare for interviews. Here is the problem I ran into, pretty simple one. Two Sum:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

And here is my solution, which time complexity is O(n) and space complexity is O(n). enter image description here

The detail shows that it's runtime is pretty slow, which is even beated by solutions with O(n)^2.

I take it for granted that lower time complexity means faster runtime. And now I'm confused. What 's the relationship betwwen run time and time complexity. And what kind of solution is expected in an interview ?

In the future, copy and paste your code as text from your IDE to the question. Images are not indexable by search engines, among other problems. See https://meta.stackoverflow.com/q/285551/215552 for a discussion. — Heretic Monkey, May 09 '17 at 15:55
If given nums = [2, 3, 3, 5] and target of 6, then the solution is nums[1]+nums[2] but your code would fail to find it because Map doesn't allow duplicates. Correctness first, performance second. — Klitos Kyriacou, May 09 '17 at 16:19

score 2 · Answer 1 · edited May 23 '17 at 11:47

2

I take it for granted that lower time complexity means faster runtime.

Not always. It depends on the size of the problem, n. Time complexity describes the performance as n grows asymptotically to infinity.

In your case, n, is just too small to make the time complexities affect the runtime. For a longer explanation please see Difference between Time Complexity and Running time.

My explanation to this behavior is that you use a hashmap, which comes with an overhead, while the other solution does not. Combined with the fact that n is small enough, their performance can be comparable.

By the way, do you need to call containsKey()? I think not, just check what put() returns, as discussed in hashmap containsKey complexity.

edited May 23 '17 at 11:47

Community

1
1

answered May 09 '17 at 16:03

gsamaras

71,951
46
188
305

1

Thank you so much, I do learn a lot form your answer. – pandakillsalot May 09 '17 at 16:12
@pandakillsalot great! You asked a nice question, that's why I upvoted. Do not forget to *accept* the answer. As your experience grows, you will feel better what time complexity really means! ;) – gsamaras May 09 '17 at 16:13
In this case, he should check what `get()` returns, not what `put()` returns. – Klitos Kyriacou May 09 '17 at 16:21

What's the relationship between time complexity and runtime?

1 Answers1