big-o Questions
4
Solved
Say I have some Python list, my_list which contains N elements. Single elements may be indexed by using my_list[i_1], where i_1 is the index of the desired element. However, Python lists may also b...
12
Solved
What are some algorithms which we use daily that has O(1), O(n log n) and O(log n) complexities?
Conker asked 20/10, 2009 at 5:33
4
Solved
I have the memoization fibonacci code and I am having trouble figuring out what the time complexity is of it:
function fibMemo(index, cache) {
cache = cache || [];
if (cache[index]) return cache...
Levulose asked 6/3, 2017 at 3:52
8
Solved
Are shift operations O(1) or O(n) ?
Does it make sense that computers generally require more operations to shift 31 places instead of shifting 1 place?
Or does it make sense the number of operati...
Anacreontic asked 31/1, 2012 at 17:5
12
Solved
I just came around this weird discovery, in normal maths, n*logn would be lesser than n, because log n is usually less than 1.
So why is O(nlog(n)) greater than O(n)? (ie why is nlogn considered to...
Lintwhite asked 8/6, 2019 at 12:34
5
Solved
I was talking with a student the other day about the common complexity classes of algorithms, like O(n), O(nk), O(n lg n), O(2n), O(n!), etc. I was trying to come up with an example of a problem fo...
Vaporization asked 6/3, 2011 at 10:29
15
Solved
According to the Wikipedia article on linked lists, inserting in the middle of a linked list is considered O(1). I would think it would be O(n). Wouldn't you need to locate the node which could be ...
Malachy asked 8/5, 2009 at 16:21
2
Solved
f (int n){
if (n<=0){
return 1;
}
return f(n-1) + f(n-1);
}
Suppose we did f(4). My thought was that it would be O(2^n), since then in order to find f(n-1) + f(n-1) we would have to push f...
Sumbawa asked 8/11, 2015 at 2:51
12
Solved
Does an algorithm exist that finds the maximum of an unsorted array in O(log n) time?
4
Solved
This question is from Cracking the Coding Interview 6th Edition, Question V1.11.
The following code prints all strings of length k where the characters
are in sorted order. It does this by gen...
5
Solved
I have been looking for an advanced levenshtein distance algorithm, and the best I have found so far is O(n*m) where n and m are the lengths of the two strings. The reason why the algorithm is at t...
Beckerman asked 30/10, 2010 at 6:17
3
Solved
This earlier question addresses some of the factors that might cause an algorithm to have O(log n) complexity.
What would cause an algorithm to have time complexity O(log log n)?
Papaw asked 9/5, 2013 at 22:13
5
Hi guys I'm using Codefights concurrently while I learn algorithims & data structures and I cant seem to solve this problem.
Given a sequence of integers as an array, determine whether it is ...
Fibrinolysis asked 4/12, 2018 at 16:24
7
Solved
This is my first course in data structures and every lecture / TA lecture , we talk about O(log(n)) . This is probably a dumb question but I'd appreciate if someone can explain to me exactly what d...
Dispirited asked 29/4, 2012 at 3:57
2
Solved
I am a bit confused on space complexity. Is this O(1) space complexity or O(N) complexity?
Since I am creating a string of size n, my guess is the space complexity is O(N) is that correct?
## thi...
Dewitt asked 7/6, 2014 at 19:31
6
Solved
I have been looking at Big O notation and have come across an operational count 2^n+n^2. I understand the practice of big O notation is to remove the constants and the low order terms, however I ca...
Hyperthyroidism asked 8/1, 2016 at 23:42
19
Solved
Can someone help explain how can building a heap be O(n) complexity?
Inserting an item into a heap is O(log n), and the insert is repeated n/2 times (the remainder are leaves, and can't violate the...
Etty asked 18/3, 2012 at 3:15
7
Solved
I have a Computer Science Midterm tomorrow and I need help determining the complexity of these recursive functions. I know how to solve simple cases, but I am still trying to learn how to solve the...
Mandate asked 20/11, 2012 at 6:28
3
When making a binary max heap, why is it better to implement it as a array based, and not a tree based (tree based as in, each node also having a pointer to it's parent)?
In terms of run time analy...
Scarper asked 5/2, 2013 at 23:37
4
Here is the question description. The first 2 suggested solutions involve DFS and BFS. This question refers to the 1st two approaches: DFS and BFS.
I have included the problem statement here for ...
Pawsner asked 17/6, 2018 at 23:17
4
Solved
Insertion sort has a runtime that is Ω(n) (when the input is sorted) and O(n2) (when the input is reverse sorted). On average, it runs in Θ(n2) time.
Why is this? Why isn't the average...
Lafountain asked 11/6, 2013 at 23:12
3
I came across this passage on page 47 of Introduction to Algorithms by Cormen et al.:
The number of anonymous functions in an expression is understood to be equal to the number of times the asym...
Switcheroo asked 1/10, 2012 at 0:23
10
Solved
I need to calculate the time complexity of the following code:
for (i = 1; i <= n; i++)
{
for(j = 1; j <= i; j++)
{
// Some code
}
}
Is it O(n^2)?
Harr asked 9/2, 2009 at 0:5
7
Solved
I'm really confused about the differences between big O, big Omega, and big Theta notation.
I understand that big O is the upper bound and big Omega is the lower bound, but what exactly does big ...
Yeager asked 29/4, 2012 at 22:56
10
Solved
It seems to be common knowledge that hash tables can achieve O(1), but that has never made sense to me. Can someone please explain it? Here are two situations that come to mind:
A. The value is an...
Barncard asked 5/5, 2010 at 7:45
1 Next >
© 2022 - 2024 — McMap. All rights reserved.