time-complexity Questions
4
Solved
I would also like to know which algorithm has the worst case complexity of all for finding all occurrences of a string in another. Seems like Boyer–Moore's algorithm has a linear time complexity.
Effeminacy asked 7/2, 2012 at 19:35
5
Solved
I am studying data-structure: singly link list.
The website says singly linked list has a insertion and deletion time complexity of O(1). Am I missing something?
website link
I do this in C++...
Samalla asked 5/11, 2016 at 20:59
23
Solved
Are there are any cases where you would prefer O(log n) time complexity to O(1) time complexity? Or O(n) to O(log n)?
Do you have any examples?
Dieback asked 9/12, 2015 at 13:25
4
Solved
For example if the list is: [2,1,2,5,7,6,9] there's 3 possible ways of splitting:
[2,1,2] [5,7,6,9]
[2,1,2,5] [7,6,9]
[2,1,2,5,7,6] [9]
I'm supposed to calculate how many times the list can be spli...
Microfarad asked 28/1, 2022 at 14:5
3
Solved
Given an integer n and array a, I need to find for each i, 1≤ i ≤ n, how many elements on the left are less than or equal to ai
Example:
5
1 2 1 1 2
Output
0 1 1 2 4
I can do it in O(N2) but ...
Heer asked 18/1, 2022 at 1:54
43
Solved
I'd prefer as little formal definition as possible and simple mathematics.
Krasner asked 28/1, 2009 at 11:10
12
Solved
I understand Big-O notation, but I don't know how to calculate it for many functions. In particular, I've been trying to figure out the computational complexity of the naive version of the Fibonacc...
Chibchan asked 11/12, 2008 at 20:20
5
Solved
Suppose there is a unsorted array A, and it contains an element x (x is the pointer of the element), and every element has a satellite variable k. So, we can get the following time complexity (for ...
Millburn asked 20/2, 2012 at 9:6
1
Solved
What is the time complexity of this particular implementation of Dijkstra's algorithm?
I know several answers to this question say O(E log V) when you use a min heap, and so does this article and t...
Aldosterone asked 21/12, 2021 at 5:36
9
Solved
The basic algorithm for BFS:
set start vertex to visited
load it into queue
while queue not empty
for each edge incident to vertex
if its not visited
load into queue
mark vertex
So I w...
Engracia asked 13/7, 2012 at 10:24
4
Solved
From https://en.wikipedia.org/wiki/Quickselect it says
"However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side – the side with the element it is se...
Beghtol asked 8/7, 2019 at 18:38
2
If the following loop structure is under Analysis of Upper bound, does it still compute to O(n^2)?
I'm confused since inner loop has a dependency on the outer loop and with each outer iteration, th...
Corbicula asked 20/10, 2021 at 21:56
2
Solved
I am trying to list time complexities of operations of common data structures like Arrays, Binary Search Tree, Heap, Linked List, etc. and especially I am referring to Java. They are very common, b...
Astera asked 3/9, 2011 at 17:19
5
Solved
I came up with this algorithm for matrix multiplication. I read somewhere that matrix multiplication has a time complexity of o(n^2).
But I think my this algorithm will give o(n^3).
I don't know ...
Underfeed asked 17/12, 2011 at 17:59
2
Solved
I am working with some code that checks if std::vector contains a given element in constant time by comparing its address to those describing the extent of the vector's data. However I suspec...
Sneed asked 23/9, 2021 at 7:0
18
Solved
So I decided to try out Codility. The first task - FrogJmp was ridiculous easy, however to my surprise I scored 44%. Solution, even if correct was obviously unacceptable in terms of performance.
O...
Terina asked 22/8, 2014 at 21:39
8
Solved
Given an infinite length sorted array having both positive and negative integers. Find an element in it.
EDIT
All the elements in the array are unique and the array in infinite in right direction.
...
Beamends asked 6/9, 2012 at 13:11
3
Solved
Given is a set S of n axis-aligned cubes. The task is to find the volume of the union of all cubes in S. This means that every volume-overlap of 2 or more cubes is only counted once. The set specif...
Kerbela asked 10/9, 2021 at 19:47
3
Solved
What time complexity (in big-O notation) is provided by the ES6 specification for the Keyed Collections (Set, Map, WeakSet, and WeakMap)?
My expectation, and I expect that of most developers, is t...
Biddie asked 27/6, 2015 at 17:59
2
Given an array with some key-value pairs:
[
{'a': 1, 'b': 1},
{'a': 2, 'b': 1},
{'a': 2, 'b': 2},
{'a': 1, 'b': 1, 'c': 1},
{'a': 1, 'b': 1, 'c': 2},
{'a': 2, 'b': 1, 'c': 1},
{'a': 2, 'b': ...
Deadwood asked 6/9, 2021 at 13:40
1
I am writing a program to determine if the Levenshtein distance between two strings is exactly 2 in linear time.
I have an algorithm which does this. I use the naive recursive approach which scans ...
Winterize asked 2/9, 2021 at 12:32
3
Solved
I needed to remove the characters in string1 which are present in string2. Here string1 and string2 have only the lower case characters a-z with given condition that the length of string1 will be g...
Forgather asked 31/8, 2021 at 9:43
15
Solved
Intro: As far as I could search, this question wasn't asked in SO yet.
This is an interview question.
I am not even specifically looking for a code solution, any algorithm/pseudocode will work.
...
Stateless asked 4/2, 2016 at 19:8
3
Solved
I was wondering what was the complexity of the replace(Key , Value) for a HashMap is.
My initial thoughts are O(1) since it's O(1) to get the value and I can simply replace the value assigned to th...
Meitner asked 25/8, 2021 at 9:27
6
Solved
My friend was asked this question in an interview:
Generate a finite but arbitrarily large binary tree in O(1). The method generate() should return a binary tree whose size is unbounded but fini...
Horaciohorae asked 26/3, 2018 at 23:20
© 2022 - 2024 — McMap. All rights reserved.