2 ms·
You don't need a recurrence relation to prove it. You can use a simple algebra where you are able to combine the complexing of algorithms. For example an O(n) a
by charcircuit 5y ago
You don't need a recurrence relation to prove it. You can use a simple algebra where you are able to combine the complexing of algorithms. For example an O(n) algorithm followed by an O(n^2) algorithm will be O(n^2). In an interview I describe how the complexity of these simpler algorithms get combined into my final answer. I assume that the interviewer and I can agree on some basic stuff like looping over an array is O(n), inserting into a heap is O(log(n)), etc.