time-complexity Questions
7
What is the complexity of std::sort() in the C++ Standard Library? Which sort is applied? Is there any rule of applying any particular sorting algorithm there?
Swanhildas asked 19/12, 2010 at 20:20
6
Solved
I am just a bit confused. If time complexity of an algorithm is given by
what is that in big O notation? Just or we keep the log?
Screamer asked 2/2, 2014 at 12:3
5
For deleting a node in the binary tree, we have to search the node. That is possible in minimum O(log N) and max O(N). Depending on the node, we have to rearrange the pointers. How do we calculate ...
Trunkfish asked 3/1, 2011 at 5:31
2
I think the time complexity of below code should be O(1) as worst case can be log 1000 base 2 or something definite. But I am not sure as it's time does vary with input and the given answer is O(n)...
Laic asked 13/7, 2022 at 12:57
5
This is the recursive implementation of the Fibonacci sequence from Cracking the Coding Interview (5th Edition)
int fibonacci(int i) {
if(i == 0) return 0;
if(i == 1) return 1;
return fibonacci(...
Vargueno asked 27/2, 2015 at 1:33
2
Solved
Some problems that are NP-hard are also fixed-parameter tractable, or FPT. Wikipedia describes a problem as fixed-parameter tractable if there's an algorithm that solves it in time f(k) · |x...
Tholos asked 28/10, 2013 at 19:57
3
Solved
I was curious why deleting a node from a double linked list is faster than a single linked. According to my lecture, it takes O(1) for a double linked list compared to O(n) for a single linked. Acc...
Austerlitz asked 8/10, 2013 at 2:3
6
Solved
I'm very new to Haskell and I'm just trying to find the sum of the first 2 million primes. I'm trying to generate the primes using a sieve (I think the sieve of Eratosthenes?), but it's really real...
Barnwell asked 1/8, 2012 at 23:21
4
Solved
I was looking at this pycon talk, 34:30 and the speaker says that getting the t largest elements of a list of n elements can be done in O(t + n).
How is that possible? My understanding is that crea...
Entourage asked 13/4, 2014 at 3:24
8
Solved
I am working through the book "Cracking the Coding Interview" and I have come across questions here asking for answers, but I need help comparing my answer to the solution. My algorithm works, but ...
Jayson asked 21/10, 2013 at 0:11
2
Solved
I'm looking for the time complexity of these methods as a function of the number of rows in a dataframe, n.
Another way of asking this question is: Are indexes for dataframes in pandas btrees (wi...
Acorn asked 15/11, 2019 at 12:3
1
Solved
The documentation for numpy.linalg.det states that
The determinant is computed via LU factorization using the LAPACK routine z/dgetrf.
I ran the following run time tests and fit polynomials of de...
Old asked 11/5, 2022 at 18:48
2
Solved
I'm wondering how sorting with an index actually works in MongoDB. There are a couple articles in the MongoDB documentation, but they don't actually describe how the sort proceeds or the time compl...
Sturdy asked 21/3, 2016 at 21:50
1
Solved
I'm currently working with Rust's HashSet and I'm trying to understand the computational complexity of the HashSet::len operation.
The Rust documentation provides information about the computationa...
Colfin asked 2/5, 2022 at 12:55
2
Solved
Can someone tell me the time complexity of the below code?
a is an array of int.
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < a.length; i++) {
if (set.contains(a...
Coshow asked 20/7, 2011 at 22:56
4
Solved
for(int i = 0; i < n; i++) {
for(int j = 0; j < i; j++){
// do swap stuff, constant time
}
}
I read that single for loop is O(N) and traversing it twice will make it O(n^2).
I watched rel...
Hunan asked 11/2, 2015 at 7:43
4
Solved
I am curious. What is the correct way to describe this using Big-O Notation?
var prices = [100, 180, 260, 590, 40, 310, 535, 10, 5, 3];
var biggest_profit = 0;
for (var i = 0; i < prices.lengt...
Tool asked 6/8, 2016 at 17:58
3
Solved
This is the Daily Coding Problem:
“Given a singly linked list and an integer k, remove the kth last element from the list. k is guaranteed to be smaller than the length of the list.
The list is v...
Haematozoon asked 21/10, 2018 at 23:47
6
Solved
Given an array with positive and negative integers, move all the odd indexed elements to the left and even indexed elements to the right.
The difficult part of the problem is to do it in-place whi...
Viewy asked 9/9, 2012 at 11:24
3
Solved
Prove that
1 + 1/2 + 1/3 + ... + 1/n is O(log n).
Assume n = 2^k
I put the series into the summation, but I have no idea how to tackle this problem. Any help is appreciated
Triplane asked 18/9, 2014 at 5:53
11
Solved
I have a (potentially large) list data of 3-tuples of small non-negative integers, like
data = [
(1, 0, 5),
(2, 4, 2),
(3, 2, 1),
(4, 3, 4),
(3, 3, 1),
(1, 2, 2),
(4, 0, 3),
(0, 3, 5),
(1,...
Moe asked 15/4, 2022 at 16:34
1
I'm trying to find a solution in C# to extending a list in O(1).
List's AddRange() method is of course an O(n) operation.
This should have been something that LinkedList supports, but LinkedList d...
Grande asked 8/1, 2020 at 8:31
6
Solved
Is the time complexity of nested for, while, and if statements the same? Suppose a is given as an array of length n.
for _ in range(len(a)):
for _ in range(len(a)):
do_something
The for statemen...
Jeane asked 2/3, 2022 at 14:28
1
I am doing an assignment for my algorithm class and I have to demonstrate that internal merge sort has a time complexity of O(n log n). To do this I made arrays ranging in length from 10,000 elemen...
Matthewmatthews asked 14/12, 2019 at 17:2
6
What is the time complexity of traversing (rows ,columns) a two dimensional array?
bool check(int array [9][9])
{
int num=0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
...
Furring asked 7/5, 2015 at 12:15
© 2022 - 2024 — McMap. All rights reserved.