asymptotic-complexity Questions
4
Solved
If f(n)=O(g(n)), then shouldn't f(n)∗log2(f(n)^c)=O(g(n)∗log2(g(n))) depend on the value of C?
Here C is a positive constant. According to me if C is large then the statement would become false an...
Coverdale asked 30/1, 2013 at 6:34
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
4
Solved
I am studying the randomized-quicksort algorithm. I realized that the running time of this algorithm is always represented as "expected running time".
What is the reason for specifying or using th...
Dreher asked 25/10, 2011 at 21:26
5
Solved
What is the difference between Big-O notation O(n) and Little-O notation o(n)?
Radius asked 1/9, 2009 at 20:22
3
Solved
Am trying to solve the given recursion, using recursion tree, T(n) = 3T(n/3) + n/lg n.
In the first level (n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3)).
In the second le...
Audrieaudris asked 10/2, 2010 at 4:37
6
I am calculating time complexity for kruskal algorithm like this (Please see the algorithm in the Image Attached)
T(n) = O(1) + O(V) + O(E log E) + O(V log V)
= O(E log E) + O(V log V)
as |E| >...
Sardis asked 6/12, 2013 at 20:16
3
I came across this question in which it was required to calculate in-degree of each node of a graph from its adjacency list representation.
for each u
for each Adj[i] where i!=u
if (i,u) ∈ E
in...
Trajectory asked 8/4, 2014 at 7:28
4
Solved
Is 2^n = Θ(4^n)?
I'm pretty sure that 2^n is not in Ω(4^n) thus not in Θ(4^n), but my university tutor says it is. This confused me a lot and I couldn't find a clear answer per Google.
Anatolio asked 30/9, 2014 at 11:13
2
METHOD (A Juggling Algorithm)
Divide the array in different sets where number of sets is equal to GCD of n and d and move the elements within sets.
If GCD is 1 as is for the above example array (n ...
Orren asked 14/6, 2014 at 15:9
3
Solved
I'm looking for a monad-free, constant access query O(1) associative array.
Consider the hypothetical type:
data HT k v = ???
I want to construct an immutable structure once:
fromList :: Folda...
Abstractionist asked 31/8, 2016 at 0:29
2
Solved
How can I find the asymptotic growth of n choose floor(n/2) ? I tried
to use the expansion and got that it is equal to
[n*(n-1)*........*(floor(n/2)+1)] / (n-floor(n/2))!
Any idea how can i go ...
Convey asked 12/9, 2014 at 17:11
2
For example, ArrayLists in Java have a resizing factor of 2. When the array that the ArrayList is wrapped around runs out of space, all the elements of that array are transferred to a new array tha...
Mikaela asked 6/9, 2018 at 2:15
3
Solved
The function must return the count of pairs of numbers in the array songs (integer array consisting of lengths of songs in seconds) such that the pairs formed add up to whole minutes.
long playlis...
Rainier asked 9/7, 2018 at 7:4
3
Solved
The algorithm std::includes takes two sorted ranges and checks whether set2 is in set1 (i.e. if each element of set2 is included in set1)?
I wonder why eel.is/c++draft says that the complexity of ...
Phiona asked 24/5, 2018 at 17:6
3
Solved
I'm wondering if its possible to express the time complexity of an algorithm that relies on convergence using Big O notation.
In most algorithmic analysis I've seen, we evaluate our function's rat...
Mulct asked 19/3, 2018 at 20:43
1
Why is time complexity O(1) of pow(x,y) while it is O(n) for x ** y?
Check comment from agf here
Ringdove asked 17/2, 2018 at 9:20
4
Solved
I'm looking at some online algorithm solutions for coding interviews, and I don't understand why this algorithm is claimed to be O(n^3).
Caveat: I understand that big-Oh notation is abused in in...
Lunkhead asked 30/11, 2017 at 22:32
6
In CLRS (Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein), for a function
f(n) = an2 + bn + c
they said
Suppose we take the constants c1 = a/4, c2 = 7a/4, and n0 = 2·max(...
Halibut asked 14/7, 2011 at 9:0
2
Solved
I struggle to define the running time for the following algorithm in O notation. My first guess was O(n), but the gap between the iterations and the number I apply isn't steady. How have I incorrec...
Welldressed asked 5/5, 2017 at 11:11
2
Solved
When I read the Church Rosser II Theorem here
Theorem (Church Rosser II)
If there is one terminating reduction, then outermost reduction will terminate, too.
I'm wondering: Is there some theorem ...
Malachy asked 22/2, 2017 at 13:57
2
Solved
I have got a question, and it says "calculate the tight time complexity for the process of inserting n numbers into a binary search tree". It does not denote whether this is a balanced tree or not....
Briarroot asked 10/3, 2013 at 12:47
2
Solved
I ran across a problem where I needed to calculate the values of very large factorials. I solved this problem in C++ in two different ways, but only want to know if my complexity analysis is accura...
Zenia asked 23/8, 2016 at 5:25
2
Solved
I had originally written an ArrayList and stored unique values (usernames, i.e. Strings) in it. I later needed to use the ArrayList to search if a user existed in it. That's O(n) for the search.
M...
Barty asked 1/8, 2016 at 5:17
1
Is there a programmatic way or eclipse plugin to calculate big-O notation for java method ?
Sideway asked 17/7, 2016 at 11:8
2
Is there a Java collection with a complexity of O(1) and not O(n) for the addAll operation, or must I implement my own collection ? With a efficient linked list the Collection1.addAll(Collection2) ...
Poyang asked 12/7, 2016 at 8:57
1 Next >
© 2022 - 2025 — McMap. All rights reserved.