Are constants always irrelevant even if they are large?For example isO(10^9 * N) == O(N) ?
Constants and Big O
big o
Big O describes how an algorithm scales; not, strictly speaking, how long it takes to execute.In your example, if the time it takes to execute over 1 item is big, then it's going to take a (non-trivially) long time to execute the algorithm, even if it's applied to one item.  But that algorithm will still increase in time linearly.  So if you hit it with 100 items, you can expect it to take 100 times as long.The same cannot be said of an O(n^2) algorithm; no matter how small the linear constant is, it's still going to eventually overtake the time it takes to execute the linear algorithm (as you increase N).The linear constant is therefore ultimately irrelevant.