I am having a really hard time trying to understand how to determine my program's runtime, is there a easy way to do it? Also, when I try to search a specific element in an array, why the time complexity is O(1) instead of O(n)? (I think it is O(n) because in the worst case you have to go through the whole array to find out if the element exists)
Asked
Active
Viewed 752 times
0
-
If it's said that the time complexity is O(1) then it's likely to be a hashtable – Martheen Feb 18 '21 at 03:04
-
You're correct: searching an array **cannot** be O(1) (unless you only ever search for the first element...). If the array is unsorted, you have to search linearly, and that's O(n). The only data structure that can approach O(1) search time is the hash table. – Kevin Anderson Feb 18 '21 at 03:05
2 Answers
3
O(n) requires you to first define what 'n' might be. Say, the task is:
Given an array a of integers, of size t, and a specific integer, x, return the first index at which x occurs in a; return -1 if x is not in a.
Then, this algorithm comes to mind:
for (int i = 0; i < a.length; i++) if (a[i] == x) return i;
return -1;
This algorithm is O(t).
What does that mean?
Well, make a graph. On the x-axis, put 'time taken' (or memory taken; you can measure space complexity or time complexity, as you wish). On the y-axis, put 't': The size of that array.
Now, start running your algorithm. First on a 1-size array, then a 2-size array, and keep going. eventually a million-size array. Graph it out.
Near the 0 point (small arrays) it's all over the place. wild swings - you're more measuring JVM bootup time, whether your music player is switching to a next track, your browser doing some work, who knows what. It's a mess. But eventually this line will stabilize. Once your input array has a few million items in it, hotspot kicking in, VM warmup, music players - these cease to have meaningful impact on the measurement.
Once the line stabilizes, what does it look like?
An O(n) algorithm says: "It looks like a non-horizontal straight line". Because if you graph y = C*x, (pick any constant for C), that looks like a non-horizontal straight line.
An O(1) algorithm looks like a horizontal line (why? Because y = C looks like that). An O(n^2) algorithm looks just like y = x^2 does if you graph it, and so on. Just like how y = 812398x^2 + 234124124x will eventually look almost exactly like y = x^2 if only you go 'far enough to the right', in O(x) notation, constant factors and eclipsed factors (The 812398 is constant, the 234124124x part is eclipsed) are ignored. This is about 'what does the graph look like, eventually?', and those aspects do not affect that at all.
Now you know what O(n) means. It is then trivial to explain why this algorithm is O(n): If you have a million numbers in your array, you have to look through potentially a million entries to figure out the answer. Whomever told you it is O(1) is wrong, or more likely you misheard them. Perhaps they were talking about:
How hard is it, given some optimized collection for just this task, to determine if a given integer x is in datastructure a which has t elements in it?
For arrays, the answer'd be O(n), but if a is a HashSet, the answer is O(1). hashsets don't require checking each element.
rzwitserloot
- 85,357
- 5
- 51
- 72
1
Searching is O(n) in an array. Its like this if you had n-items in your array there is a chance that the item you are looking for is at the end of the array. So you would need to check each element, we'll call this an action. Since there are n-elements there are n-actions hence O(n).
ac4824
- 17
- 4