big-o Questions
6
Solved
I'm trying to understand the performance of database indexes in terms of Big-O notation. Without knowing much about it, I would guess that:
Querying on a primary key or unique index will give you...
11
Solved
Why is the statement:
The running time of algorithm A is at least O(n²)
is meaningless ?
The running time of Insertion sort algorithm is at most O(n²)
Is it Correct?
I tried the net but...
Soupspoon asked 4/3, 2013 at 6:45
8
I have seen that in most cases the time complexity is related to the space complexity and vice versa. For example in an array traversal:
for i=1 to length(v)
print (v[i])
endfor
Here it is easy...
Mounts asked 8/9, 2013 at 16:41
2
I have to calculate the cost of this algorithm.
I was thinking about an exponential cost. I tried the recurrence relation. 4*T(n/4) + c*n and at the end it's ((4^n) - 1)/3.
Is that correct? Are t...
Gomar asked 2/7, 2018 at 9:50
3
I was studying big O notation for a technical interview and then I realized that javascript's indexOf method may have a time complexity of O(N) as it traverses through each element of an array and ...
Server asked 13/9, 2016 at 6:30
32
Solved
I am learning about Big O Notation running times and amortized times. I understand the notion of O(n) linear time, meaning that the size of the input affects the growth of the algorithm proportiona...
Gingersnap asked 21/2, 2010 at 20:5
3
Solved
Consider two functions of SymPy symbols e and i:
from sympy import Symbol, expand, Order
i = Symbol('i')
e = Symbol('e')
f = (i**3 + i**2 + i + 1)
g = (e**3 + e**2 + e + 1)
z = expand(f*g)
This ...
Xerosere asked 29/8, 2017 at 14:54
8
Let's say that the algorithm involves iterating through a string character by character.
If I know for sure that the length of the string is less than, say, 15 characters, will the time complexity ...
8
Solved
As per my understanding, I have calculated time complexity of Dijkstra Algorithm as big-O notation using adjacency list given below. It didn't come out as it was supposed to and that led me to unde...
Wooster asked 24/10, 2014 at 12:24
17
Solved
If I have some R list mylist, you can append an item obj to it like so:
mylist[[length(mylist)+1]] <- obj
But surely there is some more compact way. When I was new at R, I tried writing lappe...
Sartorial asked 13/3, 2010 at 0:14
8
Solved
Recently, I noticed some people mentioning that std::list::size() has a linear complexity.
According to some sources, this is in fact implementation dependent as the standard doesn't say what the c...
Antebellum asked 23/10, 2008 at 8:8
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
4
Solved
What is the complexity of the addAll method of PriorityQueue. Does it add one element at a time resulting in O(n log n) or does it use a build heap process that creates a heap out of unordered elem...
Astroid asked 14/1, 2013 at 1:10
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
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
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
6
Solved
Given the function below:
int f(int n) {
if (n <= 1) {
return 1;
}
return f(n - 1) + f(n - 1);
}
I know that the Big O time complexity is O(2^N), because each call calls the function tw...
Gavrilla asked 8/4, 2017 at 18:37
8
Solved
Is 2(n+1) = O(2n)?
I believe that this one is correct because n+1 ~= n.
Is 2(2n) = O(2n)?
This one seems like it would use the same logic, but I'm not sure.
6
Solved
Talking about Big O notations, if one algorithm time complexity is O(N) and other's is O(2N), which one is faster?
8
Solved
Question
Hi I am trying to understand what order of complexity in terms of Big O notation is. I have read many articles and am yet to find anything explaining exactly 'order of complexity', even o...
Voiced asked 19/12, 2013 at 18:9
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
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
© 2022 - 2025 — McMap. All rights reserved.