Questions tagged [time-complexity]
The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and lower order terms.
time-complexity
10,266
questions
-8
votes
0
answers
69
views
Why does caching/memoization in a sorting comparator increase runtime instead of reducing it? [closed]
I'm solving a problem on Leetcode where I need to sort an array of integers based on their mapped values using a custom digit mapping. I’ve implemented two versions of the solution to address this ...
- 93
0
votes
1
answer
34
views
Performance Comparison Between Tabulation and Memoization for Dynamic Programming [closed]
I'm delving into dynamic programming and trying to understand the general performance differences between tabulation and memoization. Both techniques aim to optimize recursive algorithms by storing ...
- 376
0
votes
0
answers
28
views
Optimizing Code with Bitwise Operators : How Does That Really Work? [closed]
How do bitwise operators (like AND, OR, XOR, left shift, and right shift) manipulate binary data at the bit level, and what are some practical examples of their usage in optimizing code performance or ...
-4
votes
1
answer
70
views
does spacing between statements, indentation and comments in code affects its time and space complexity? [closed]
I'm trying to understand how code formatting and documentation impacts the performance of a program
Spacing between statements: having more or fewer blank lines between code statements.
Indentation: ...
0
votes
1
answer
58
views
Time Complexity for finding k smallest elements in an array of size n
I came across 3 approaches for the problem.
Sort the array and find the k elements O(nlog(n))
Using minHeap, heapify in O(n) time and extract k elements O(klog(n)); total = O(n + klog(n))
Using ...
- 40
4
votes
0
answers
205
views
Finding repeating sequences with less than O(n^2) time complexity
Is it possible to find repeating sequences of any length (without complete overlaps) with an average time complexity less than O(n^2) ?
For example, take a string like this:
0 1 2 ...
- 1,644
0
votes
0
answers
18
views
Time Complexity of my Subset Sum Problem's Solution [duplicate]
class Solution {
public:
vector<vector<int>> subsetsRec(int i,vector<int>& nums) {
vector<vector<int>> ans;
if(i==0){
vector<int>...
4
votes
1
answer
114
views
How to prove a problem is unsolvable in a certain Time Complexity?
While discussing the Local Minimum in n x n Matrix Problem with my professor, he suggested that there exists a solution with O(log n) time complexity for this problem. Now, I'm fairly sure he is wrong,...
- 53
0
votes
2
answers
145
views
Find unique or combination for given array
I have an array of numbers of size n, select all possible distinct increasing subsequence of the array, for each subsequence find the bitwise OR value and return them as result in increasing order.
...
- 87
2
votes
1
answer
82
views
Modified Dijkstra - Time Complexity?
I am solving the Leetcode Problem 787. Cheapest Flights Within K Stops.
Basically this is single source shortest path, but with max k steps allowed. So, we can't use normal Dijkstra algorithm, where ...
- 59
3
votes
4
answers
134
views
sorting algorithm in O(n) according a specific condition
Given an array A with n−1 numbers where n = 2^k
for some integer k. One of the values appears exactly n/2
another appears exactly n/4, and so on. More formally, for all 1 ≤ k ≤ log n exists a value ...
- 31
0
votes
1
answer
65
views
What's the difference between O(n) and O(n+n^1/2) in algorithm?
I watched an online course which mentioned that O(n) and O(n + n^(1/2)) are equivalent in algorithms.
I'm curious about why the n^(1/2) part can be ignored. What is the reason for this omission? I ...
- 25
2
votes
0
answers
79
views
What is the Time Complexity of a function if there is an upper limit to the variable
I have the following piece of code.
void foo(int n){
n=n*n;
for (int i=0;i<n;i++){
if(n<10)
cout << i;
else
break;
}
}
Now I wanted to ask if the time complexity ...
2
votes
1
answer
77
views
Why can't a time complexity O(2^N ) be reduced to O(2*2*2*...*2^0)=O(1)?
Consider the time complexity O(5N2). By eliminating the constant factor 5, we represent the time complexity as O(N2).
Now, if we have a time complexity of O(2N), we can rewrite this as O(2⋅2N-1). Then ...
- 21
1
vote
0
answers
42
views
Time and space complexity of a given Branch-and-Bound algorithm
I need to calculate the time and space complexity of a Branch-and-Bound algorithm, to solve a problem. The problem is: On a chess board, the knight needes to move, from a initial to a end point, doing ...
