Should we ignore constant k in O(nk)?
Was reading CLRS when I encountered this:
Why do we not ignore the constant k in the big o equations in a. , b. and c.?
In this case, you aren't considering the run time of a single algorithm, but of a family of algorithms parameterized by k. Considering k lets you compare the difference between sorting n/n == 1 list and n/2 2-element lists. Somewhere in the middle, there is a value of k that you want to compute for part (c) so that Θ(nk + n lg(n/k)) and Θ(n lg n) are equal.
Going into more detail, insertion sort is O(n^2) because (roughly speaking) in the worst case, any single insertion could take O(n) time. However, if the sublists have a fixed length k, then you know the insertion step is O(1), independent of how many lists you are sorting. (That is, the bottleneck is no longer in the insertion step, but the merge phase.)
- Smallest number that cannot be formed from sum of numbers from array
- What's a fast way to identify all overlapping sets?
- minimax losing only in one case of tic-tac-toe
- Is the inorder predecessor of a node with no left subtree and being the left child of its parent always its grandparent?
- (a * b) / c MulDiv and dealing with overflow from intermediate multiplication
- What is the fastest way to compute sin and cos together?
- How to find optimum combination for Cutting Stock Problem using Knapsack
- How fast can you detect if two rows in an n by n binary matrix have (at least) two bits in a common position?
- MaxCounters (lesson 4 in codility) - 100% correctness but 60% on efficiency, why?
- How to calculate rounded corners for a polygon?
- Is the Inorder Predecessor of a Node with a Left Subtree Always a Leaf Node in a Binary Search Tree?
- Codility Leader Algorithm in JavaScript
- Tricky Google interview question
- Java problem time limit exceeded issue
- Can we get a better complexity than O(n) for cumulative sum while using multithreading?
- Fastest method to define whether a number is a triangular number
- What is a plain English explanation of "Big O" notation?
- How can I get the length of repeating decimal?
- Splitting dag dependencies in python
- How to find the time comlexity when comparing sublists?
- Clarification on `length = prefixTable[length - 1]` vs. `length = length - 1` in the KMP Algorithm
- Swapping two numbers using only two variables
- Fastest way to fill an array with a single value
- Algorithm for minimizing the amount of lines to draw?
- Convert Excel Column Number to Column Name in Matlab
- Find n-element in sequence. How to speed up the programm (time) for n > 10^6?
- O(n log n) algorithm to find number of large inversions
- Algorithm for drawing lines with 90-degree angles
- Depth First Search v.s. Greedy Best First Search
- How to improve pandas DF processing time on different combinations of calculated data