FAQ Database Discussion Community

Time complexity of python code for finding the longest word that can be made of other words in the list

python,performance,big-o,time-complexity
I am preparing for some coding interviews and came up with a solution to the following problem: "Find longest word that can be made of other words in a list of words". I have a hard time figuring out the time complexity of my algorithm. It would be great, if...

Binary search - worst/avg case

search,big-o,time-complexity,complexity-theory,binary-search
I'm finding it difficult to understand why/how the worst and average case for searching for a key in an array/list using binary search is O(log(n)). log(1,000,000) is only 6. log(1,000,000,000) is only 9 - I get that, but I don't understand the explanation. If one did not test it, how...

How to optimize for time?

performance,time,time-complexity
I'm trying to understand if there is a difference in speed when executing the following lines of code in a computer program: myarray[1] = 5; return myarray[1]; myarray[0] = 5; return myarray[0]; x = 5; return x; x = 5; y = x; return y; return 5; From what I...

sorting component-wise multi value (SIMD) array

algorithm,sorting,time-complexity,sse,simd
I'm trying to find an O(n∙log(n)) sorting method to sort several arrays simultaneously so that an element in a multi-value array will represent elements from 4 different single value arrays and the sorting method would sort the multi-value elements. For example: For a given 4 single value arrays An, Bn,...

How to optimize a list search in SML/NJ?

arrays,list,tuples,time-complexity,sml
I am writing a piece of code in SML/NJ and need, at some point, to access a list, which I have already created. I know that, in C, for example, accessing an array takes constant time. So, I thought that that would be the case for ML as well. Apparently,...

HashMap vs. ArrayList insertion performance confusion

java,arraylist,hashmap,time-complexity,asymptotic-complexity
From my understanding a hashmap insertion is O(1) and for an arraylist the insertion is O(n) since for the hashmap the hashfunction computes the hashcode and index and inserts the entry and an array list does a comparison every time it enters a new element.

time complexity of this given data structure

c++,algorithm,time-complexity
I am just starting to learn about the time complexities and I just want to make sure I am getting this right. if we have a unordered_map<string, set<int>> note that organized as hash tables that never allow the load factor to exceed some constant. Lets say string are business names...

Multiple recursive calls

c++,recursion,time-complexity
I know what a recursive function is and how I can visualize every recursive call on top of the stack. But I have no idea how to think when the function make multiple calls to itself like float foo(int n){ int a = 0; for(int i = 0; i <...

What is the big-O complexity of this code

big-o,time-complexity
Whats the big-O notation of this code? for( int i=1; i<2n; i++) x=x+1; My answer = O(2*n) Is this correct?...

Why, algorithm and data structure, both are not considered together when doing Big O complexity analysis?

algorithm,data-structures,big-o,time-complexity
I have been reading about algorithms and data structures & their performance characteristics. I want to understand - How running time of a program is affected by the Big O complexity analysis of a particular algorithm against a particular data structure. For e.g. in a Red-Black Tree structure, searching in...

Time complexity of Andrew's algorithm (complex hull)

algorithm,time-complexity,convex-hull
According to Wikibooks, the Andrew's algorithm runs in linear time if all the points are already sorted. We will take the case of sorted points. However, in the pseudo code it says: for i = 1, 2, ..., n: while L contains at least two points and the sequence of...

Resolution easy recurrence equation

time-complexity,recurrence-relation
I have to find the recurrence equation of following function. public static boolean f(int[] a) { return fr(a, 0); } private static boolean fr(int[] a, int i) { int n = a.length; if(i >= n-1) return true; else if(a[i] > a[i+1]) return false; else return fr(a, i+1); } I think...

Why O(2^log(n)) = O(n) and it is not a exponential run time?

math,time-complexity,complexity-theory
Why is O(2^log(n)) equivalent to O(n)? Also why is this considered as an exponential run time and not a polynomial run time?

Why DFS doesn't check children of a node, that was chosen for development, for a goal state

algorithm,search,time,time-complexity,depth-first-search
Sorry if my grammar is far from being perfect, English is not my native language. If i understand correctly, DFS does a goal test for a node only if it was chosen for development and not while it's been generated. It seem odd to me because after DFS chooses a...

Where do exponent denominators (fractional exponents) in big-O time complexity come from?

algorithm,big-o,time-complexity
In algorithm descirptions, I sometimes encounter time complexities that look like: O(n29/20+m7/3). I see where + and numerators in powers come from: + means successive loops, and numerators mean nested loops. For example this (useless) algorithm has O(n2+m) time complexity: public int compute(int n, int m) { int answer =...

Time Complexity of Dependent for loop

algorithm,loops,time-complexity,complexity-theory,probability
string str = "abcdefghijklmnopqrstuvwxyz"; int sum = 0; for(int i=0; i<str.length; i++) { int val = str[i]; while(val > 0) { sum = val % 62; val = val / 62; } } I know that parent loop executes n+1 time and the child loop executes (val)^(1/62) times. For parent...

Time complexity of double invarient for loops

algorithm,time-complexity
I have an array of lists(i.e. each cell in the array contains a list). The length of the array is n and the sum of all the lengths of all the lists is k I want to iterate over all the list elements(in the whole array): for(int i = 0;...

Calculating the complexity of an algorithm with 3 loops

algorithm,time-complexity,complexity-theory
I tried to solve the following exercise : What is the order of growth of the worst case running time of the following code fragment as a function of N? int sum = 0; for (int i = 1; i <= N; i++) for (int j = 1; j <=...

Determining the Big O complexity for “for” loops.

big-o,time-complexity
I have 3 for problems I having trouble determing the Big O complexity for. A. int x = 0; for ( int y = 1; y <= n * n; y++) for ( int z = 1; z < y; z++ ) x++; I want to say n3 because the...

Longest Increasing Subsequence code in O(N)?

python,algorithm,time-complexity,longest-substring
Someone asked me a question Find the longest alphabetically increasing or equal string composed of those letters. Note that you are allowed to drop unused characters. So ghaaawxyzijbbbklccc returns aaabbbccc. Is an O(n) solution possible? and I implemented it code [in python] s = 'ghaaawxyzijbbbklccc' lst = [[] for i...

Big O notation for the complexity function of the fourth root of n

algorithm,math,big-o,time-complexity,complexity-theory
I am expected to find the Big O notation for the following complexity function: f(n) = n^(1/4). I have come up with a few possible answers. The more accurate answer would seem to be O(n^1/4). However, since it contains a root, it isn't a polynomial, and I've never seen this...

What part of my code is making my performance suffer? (Codility's MaxCounter)

java,algorithm,data-structures,big-o,time-complexity
I have the following problem: You are given N counters, initially set to 0, and you have two possible operations on them: increase(X) − counter X is increased by 1, max counter − all counters are set to the maximum value of any counter. A non-empty zero-indexed array A of...

What is the approach to solving a recurrence relation when I have more than one recurrent function calls on the right-hand side of the equation?

algorithm,math,recursion,time-complexity
I am trying to analyze the complexity of the function call to PEL(A[1..n]) where n is a certain power of 3 and PEL is defined by the following algorithm: function PEL(A[m..n]){ if(n - m <= 1) return 1; else { p := [(n - m + 1)/3]; MAKE(A[m..n]); PEL(A[m..n +...

time complexity for following function

c#,optimization,time-complexity
Can any tell the time complexity of following block of code private static void Multiply(int num1, int num2) { long p,b,h1,h2,l1,l2,z0,z1,z2,m1,m2; p = num1.ToString().Length-2; b=Convert.ToInt32(Math.Pow(10,Convert.ToDouble(p))); l1=num1%b; h1 = num1 - l1; l2 = num2 % b; h2 = num2 - l2; m1=num1 / b; m2=num2 / b; z0 = l1*(m1+m2);...

Get distance of elements inside an array?

ruby-on-rails,algorithm,time-complexity
I'm struggling with a rather easy task which has an array of non-negative integers where I need to return the closest distance. Array: arr = [8, 24, 3, 20, 1, 17] Solution: 2, arr[2]-arr[4] Sor far, I've only managed to write a O(n^2) solution, which is obviously not good enough:...

Time complexity of LinkedList, HashMap, TreeSet? [closed]

java,collections,time-complexity
I am a student of CS, learning about Java Collections. At my school we have received a chart with with time complexity of different operations on data structures. There are some things in the chart that don't make sense to me. Linked List It says that time complexity for inserting...

What is the time complexity of lookups and inserts in a Delphi TList?

delphi,time-complexity,tlist
The "TList" object in Delphi confuses me a bit with its "items[i]" property. This property hints that the TList might internally index all its list items in some kind of array. I am fully aware though that such indexed properties can be handled arbitrarily inside objects (in this case e.g....

C# Algorithm Time Complexity

c#,algorithm,time-complexity
I have this code and I am trying to work out the time complexity of it when n=2, n=4 and n=6. Can anyone help me? I'm confused as how I do it? Big-O Notation please. using System; class TimeComplexityTest { public static void Main( string[] args) { int n; Console.WriteLine("Please...

What is time complexity for the following code?

time-complexity
It seems the complexity of the following code should be O(n^2) but it's O(n), how? void fun(int n, int arr[]) { int i = 0, j = 0; for(; i < n; ++i) while(j < n && arr[i] < arr[j]) j++; } ...

Time complexity of Boggle solver

python,algorithm,big-o,time-complexity
Here is a (ugly) algorithm for finding all words in Boggle: d = {'cat', 'dog', 'bird'} grid = [ ['a', 'd', 'c', 'd'], ['o', 'c', 'a', 't'], ['a', 'g', 'c', 'd'], ['a', 'b', 'c', 'd'] ] found = {} N = 4 def solve(row, col, prefix): if prefix in d...

time complexity analysis for finding the maximum element

algorithm,big-o,time-complexity,lower-bound
I've encountered a homework problem. which of these is an asymptotically tight upper bound for the best-case running time of an optimal algorithm that finds the maximum element in an arbitrary array of integers of size n (1) O(logn) (2) O(n^2) (3) O(n) (4) O(1) (5) O(nlog(n)) Based on my...

I'm timing a function that has a runtime of O(n^3) but my timing results do not show this, why is this happening?

matlab,big-o,time-complexity
numberOfTrials = 10; numberOfSizes = 6; sizesArray = zeros(numberOfSizes, 1); randomMAveragesArray = zeros(numberOfSizes, 1); for i=1:numberOfSizes N = 2^i; %x=rand(N,1); randomMTimesArray = zeros(numberOfTrials, 1); for j=1:numberOfTrials tic; for k=1:N^3 x = .323452345e-999 * .98989898989889e-953; end randomMTimesArray(j) = toc; end sizesArray(i) = N; end randomMPolyfit = polyfit(log10(sizesArray), log10(randomMAveragesArray), 1); randomMSlope =...

How can I reason about big O for various functions?

algorithm,time-complexity,complexity-theory
Consider the following functions: f(n) = 2^n g(n) = n! h(n) = n^logn Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true? (A) f(n) = O(g(n)); g(n) = O(h(n)) (B) f(n) = \Omega(g(n)); g(n) = O(h(n)) (C) g(n) = O(f(n)); h(n) = O(f(n))...

Time complexity of if-else statements in a for loop

if-statement,for-loop,time-complexity,asymptotic-complexity
Let A[1, …, n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is θ(m). Consider the following program fragment written in a C like language: Case 1 :- counter = 0; for (i = 1; i < =...

A linear time, constant space algorithm for finding an element with 1 occurrence in a list [duplicate]

algorithm,list,constants,time-complexity,space-complexity
This question already has an answer here: Finding a single number in a list [duplicate] 11 answers Given a list of n integers, where every integer in the list exists twice, except for one element, which exist once in the list. For example, [1 3 3 6 2 7...

How to optimize my code for finding the count of all integral medians for all possible integral triangles with a <= b <= c <= 100000?

c,algorithm,math,time-complexity
I am doing the solution for this problem from Euler Project Problem 513, Integral median: ABC is an integral sided triangle with sides a≤b≤c. mc is the median connecting C and the midpoint of AB. F(n) is the number of such triangles with c≤n for which mc has integral length...

What is the time complexity of the given algorthm?

algorithm,time-complexity,complexity-theory,asymptotic-complexity,big-theta
x=0 for i=1 to ceiling(log(n)) for j=1 to i for k=1 to 10 x=x+1 I've included the answer I've come up with here: I think the time complexity is θ(n^2 log(n)), but I am not sure my logic is correct. I would really appreciate any help understanding how to do...

Why is the std::map::operator[] logarithmic in complexity relative to number of keys?

c++,dictionary,time-complexity
Can someone explain why the std::map subscript operator method is logarithmic in complexity (as opposed to linear), relative to the number of keys in the mapping? (I'm sure this a pretty basic question but I'm new to computational complexity)...

Explain the time complexity of these grouping functions

c++,algorithm,inheritance,time-complexity
Here I have 800 derived classes of Base and a list of 8000000 objects of these types, which can be of any order. The goal is to separate the list into the 800 types as efficiently as possible. Here I have written two functions to do that. The first is...

Fibonacci Sequence - Time Complexity

time-complexity
Given that fib(n)=fib(n-1)+fib(n-2) for n>1 and given that fib(0)=a, fib(1)=b (some a, b >0), which of the following is true? fib(n) is Select one or more: a. O(n^2) b. O(2^n) c. O((1-sqrt 5)/2)^n) d. O(n) e. Answer depends on a and b. f. O((1+sqrt 5)/2)^n) Solving the Fibonacci sequence I...

Time complexity of recursive permutation printer

python,algorithm,time-complexity,permutation
While trying to explain recursive algorithms to generate permutations in lexicographic order, I provided this simple algorithm: def permute(done, remaining): if not remaining: print done return sorted_rem = sorted(remaining) l = len(sorted_rem) for i in xrange(0, l): c = sorted_rem[i] # Move to c to done portion. done.append(c) remaining.remove(c) #...

what would be the best case scenario of merging two sorted array?

arrays,merge,time-complexity
i know that merging two sorted array takes O(m+n) time where m and n are the length of two arrays. maximum number of comparison would be (m+n-1). But one of my school teacher said that only average and worst case takes O(m+n) time. best cases takes O(1) time. here i...

Performing the fastest search - which collection should i use?

java,search,collections,time-complexity
I know: If you need fast access to elements using index, ArrayList is your answer. If you need fast access to elements using a key, use HashMap. If you need fast add and removal of elements, use LinkedList (but it has a very poor seeking performance). In order to perform...

How to store sparse matrix?

c++,time-complexity,sparse-matrix
I need to implement 2 types of storing sparse matrix in C++: Linked List Array (effective way) Space complexity is very important here. What are the most effective ways to do it? ...

Big-O complexity of a piece of code

algorithm,time-complexity
I have a question in algorithm design about complexity. In this question a piece of code is given and I should calculate this code's complexity. The pseudo-code is: for(i=1;i<=n;i++){ j=i do{ k=j; j = j / 2; }while(k is even); } I tried this algorithm for some numbers. and I...

How many times is x=x+1 executed in theta notation in terms of n?

algorithm,language-agnostic,time-complexity,complexity-theory,analysis
I'm taking Data Analysis and Algorithms in the Summer. The question: Find a Θ-notation in terms of n for the number of times the statement x = x + 1 is executed. for i = 1 to 526 for j = 1 to n^2(lgn)^3 for k = 1 to n...

time complexity of non-inplace binary search

big-o,time-complexity,complexity-theory,binary-search
Assuming that binary search is called upon a subarray of approximately length n/2 and that there are at most three comparions at a level I came up with T(n) = T(n/2) + 3 as a recurrence relation. But: When I call binarySearch recursively isn't the cost of the slice proportional...

Is it better complexity wise to use the map() function in python or a comprehension? [duplicate]

python,python-2.7,time-complexity,space-complexity
This question already has an answer here: Python List Comprehension Vs. Map 8 answers As the question states. map(f, iterable) can be written as [f(x) for x in iterable]. Which is better to use? And why? As an example, I would like to convert a list of strings to...

time complexity of randomized array insertion

arrays,algorithm,random,insert,time-complexity
So I had to insert N elements in random order into a size-N array, but I am not sure about the time complexity of the program the program is basically: for (i = 0 -> n-1){ index = random (0, n); (n is exclusive) while (array[index] != null) index =...

What is an Approximation Factor?

time-complexity,complexity-theory
How is an approximation Factor different than time-complexity? I have heard, for example, of polynomial algorithms with exponential factors, what does that mean? Does that mean it is not technically in polynomial time?

Need to calculate Time and Space Complexity of a program

python,time-complexity,space-complexity
How would I calculate the time and space complexity of the following program? import random a = [random.randint(1,100) for i in xrange(1000000)] print a a.sort() print a ...

How to understand the time complexity of Kademlia node operation

I'm now learning Kademlia network by reading the classical paper Kademlia: A Peer-to-peer Information System Based on the XOR Metric. I want to understand the complexity of its operation but still cannot figure it out. In the 3 Sketch of proof section, the paper gives two definitions: Depth of a...

sum of absolute matrix

java,algorithm,time-complexity,tail-recursion
Here is a question from previous HackerEarth Challenge - Roy has a matrix of size NxN. Rows and Columns are numbered from 0 to N-1. jth column of ith row contains absolute difference between i and j. In other words, Matrix[i][j] = abs(i-j) where 0 ≤ i, j < N....

Proposed analysis of algorithm

algorithm,recursion,time-complexity,asymptotic-complexity
I have been practicing analyzing algorithms lately. I feel like I have a pretty good understanding of analyzing non-recursive algorithms but I am unsure, and have just begun to embark on a full understanding of recursive algorithm as well. Although, I have not had a formal check on my methods...

Why do we ignore co-efficients in Big O notation?

algorithm,big-o,time-complexity,complexity-theory
While searching for an answer of Big O Notation I have googled a lot and have also seen many SO answers like link 1, link 2, link 3 and many more, but still I have not clearly understood some points. One of them is why do we ignore / remove...

Time complexity of union

algorithm,union,time-complexity,dijkstra
We have a directed graph G=(V,E) ,at which each edge (u, v) in E has a relative value r(u, v) in R and 0<=r(u, v) <= 1, that represents the reliability , at a communication channel, from the vertex u to the vertex v. Consider as r(u, v) the probability...

What is the Big-O complexity of this code?

big-o,time-complexity
What would be the big O for void fun(int n) { for(i=1; i<=n; i=i+2) { } } My answer: O(log n) (since the i values is 1,3,5,7,9 reducing by 2 overall) void fun(int n) { for(i=1; i<=n; i=i+2) { } } My answer: O(log n), since this is quadratic (i...

Solving a complex recurrence relation for the Traveling Salesman

algorithm,math,time-complexity,computer-science,recurrence-relation
I need to solve the exact time complexity for the brute force version of the Traveling Salesman using a recurrence relation. I've worked out the recurrence relation to be as follows: T(n)=T(n-1)*(n-1)+1 But I'm having trouble reducing that that to a closed form of the function, and thus get the...

Can you do addition/multiplication with Big O notations?

algorithm,big-o,time-complexity
I'm currently taking an algorithm class, and we're covering Big O notations and such. Last time, we talked about how O (n^2 + 3n + 5) = O(n^2) And I was wondering, if the same rules apply to this: O(n^2) + O(3n) + O(5) = O(n^2) Also, do the following...

Why does this loop return a value that's O(n log log n) and not O(n log n)?

loops,for-loop,time-complexity,nested-loops,asymptotic-complexity
Consider the following C function: int fun1 (int n) { int i, j, k, p, q = 0; for (i = 1; i<n; ++i) { p = 0; for (j=n; j>1; j=j/2) ++p; for (k=1; k<p; k=k*2) ++q; } return q; } The question is to decide which of the...

Hash “has_key” complexity in Ruby

ruby-on-rails,ruby,algorithm,hash,time-complexity
I have a hash vars = {"a" => "Name", "b" => "Address" , "c" => "Phone"}. I want to check the performance of this line : vars.has_key(:b)? Is it O(1) or O(size of hash) ?...

How can I tell how many times these nested statements will execute?

algorithm,sorting,big-o,time-complexity,complexity-theory
I have the following pseudocode: SelectionSort(A) n = A.length for j=1 to n-1 smallest = j for i=(j+1) to n if A[i] < A[smallest] smallest = i exchange A[j] with A[smallest] I think that the first for-loop test will execute n times, and the nested for-loop will execute 1 +...

What is the complexity of these two string based algorithms?

java,performance,algorithm,big-o,time-complexity
I have written these two algorithms to check a string for duplicate characters (ABBC, AAAC). The first uses the hashset data structure, whilst the second relies purely on iteration. Algorithm 1 String s = "abcdefghijklmnopqrstuvwxxyz"; public boolean isUnique(String s) { Set<Character> charSet = new HashSet<Character>(); for(int i=0; i<s.length(); i++) {...

Would this algorithm run in O(n)?

algorithm,big-o,time-complexity,complexity-theory,asymptotic-complexity
Note: This is problem 4.3 from Cracking the Coding Interview 5th Edition Problem:Given a sorted(increasing order) array, write an algorithm to create a binary search tree with minimal height Here is my algorithm, written in Java to do this problem public static IntTreeNode createBST(int[] array) { return createBST(array, 0, array.length-1);...

run time of this Prime Factor function?

algorithm,time-complexity
I wrote this prime factorization function, can someone explain the runtime to me? It seems fast to me as it continuously decomposes a number into primes without having to check if the factors are prime and runs from 2 to the number in the worst case. I know that no...

c++ code time complexity of && operator

c++,time-complexity
I have the following 2 codes: int i=0; while(i<=1000000000 && i!=-1) { i++; } I think the run-time complexity is 4 billion In the while condition is 3 operations (i<=1000000000),(i!=-1) and && , and int i=0; while(i!=-1) { if(i>=1000000000) break; i++; } Which I think the run-time complexity is 3...

What is the time complexity of the following code

time-complexity
int rand7() { int vals[5][5] = { { 1, 2, 3, 4, 5 }, { 6, 7, 1, 2, 3 }, { 4, 5, 6, 7, 1 }, { 2, 3, 4, 5, 6 }, { 7, 0, 0, 0, 0 } }; int result = 0; while (result ==...

Asymptotic analysis of functions

algorithm,time-complexity,complexity-theory,asymptotic-complexity
I have the following function to prove that its time complexity is less or equal to O(xlogx) f(x) =xlogx+3logx2 I need some help to solve this....

Determining the big-O runtimes of loop with inner loop repeat time is const

algorithm,math,big-o,time-complexity,complexity-theory
I have a function for(int i=0;i<n; i++) { b[i]=0; for(int j=0;j<5;j++) { b[i]=a[j+i] } } I need to calculate big-O of above function. My answers is: Inner loop run 5n time => O(n). So the total complexity is O(n). I think I have a mistake in my calculations, but I...

Asymptotic complexity for typical expressions

time-complexity,asymptotic-complexity
The increasing order of following functions shown in the picture below in terms of asymptotic complexity is: (A) f1(n); f4(n); f2(n); f3(n) (B) f1(n); f2(n); f3(n); f4(n); (C) f2(n); f1(n); f4(n); f3(n) (D) f1(n); f2(n); f4(n); f3(n) a)time complexity order for this easy question was given as--->(n^0.99)*(logn) < n ......how?...

radix sort (java implementation) complexity

this is my first question so I hope I haven't broken any rules. I have finally just managed to write code for the Radix Sort algorithm but I am wondering if I have done it wrong. What makes me think that is that my algorithm looks of complexity O(n^3) but...

Why is only one of the given statements about complexity classes correct? [closed]

algorithm,big-o,time-complexity,complexity-theory
Apparently the correct answer to the following question is (C), but why are the other options not correct until we know the value of n? If n=1, all of these seem correct except (B)! Where am I going wrong? Which of the following is not O(n2)? (A) 1510 * n...

Complexity in terms of Θ

java,time-complexity
I know that the following code is considered "Linear or Θ(n)" what I don't understand is how we know that it is. Assuming that n has been declared appropriately and has been set to a value. int sum = 0; for (int i = 0; i < n*2; i++ )...

What complexity .equals() is in immutable.js

javascript,time-complexity,immutable.js
I'm comparing two deeply nested immutable Maps in immutable.js. What is the complexity of the .equals() function?

TIme complexity of various nested for loops

loops,for-loop,big-o,time-complexity,asymptotic-complexity
Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount. loop 1 ---- for (int i = 1; i <=n; i *= c) { // some O(1) expressions } loop 2 ----- for (int i = n; i >...

Why is my Sieve of Eratosthenes so slow?

python,performance,algorithm,time-complexity,primes
Im solving some problems on Project Euler and had to generate 2 million primes to solve a problem. My implementation of the Sieve of Eratosthenes turned out to be EXTREMELY slow but I don't quite know why. Could someone please explain the major problems with this implementation. I thought it...

Perform insert,search and delete queries on an array in less than O(n) time and using O(1) auxillary space

arrays,data-structures,time-complexity
I am given an array of numbers and allowed to preprocess them . There are 3 types of queries : Insert(x) which inserts an element "x" into the array. Delete(x) which deletes an element "x" from the array (assume x is present in the array) Find(x) which returns if "x"...

Is the time complexity of this code O(N^2)

java,algorithm,performance,substring,time-complexity
This is a solution of mine for one of the problems in leetcode. Through my deductions, I concluded it to have an overall O(N^2) time complexity. However, I would like to get a confirmation on this just so that I don't continue making the same mistakes when it comes to...

Wouldn't this algorithm run in O(m log n)?

java,algorithm,runtime,big-o,time-complexity
I am working on an interview question from Glassdoor Software Engineer The question is     Given a list of one million numbers, how will you find the top n numbers from the list in an efficient way Here is a solution an author gave from same link create a...

O notation proof for exponents and power

algorithm,big-o,time-complexity,complexity-theory,exponential
I am trying to prove that 4^n is not in the order of O(2^n). Is this a valid method ? 4^n >= c*2^n => 4^n/2^n >= c => 2^n >= c I got lost here......

Time complexity of inserting into table with PRIMARY KEY on HASH index

mysql,hash,time-complexity,unique-index
I just found out that PRIMARY KEYs on HASH-indexed columns in MEMORY tables are themselves HASH indices, as shown by the following: mysql> CREATE TABLE `test_memory` ( -> `id` int(11) NOT NULL AUTO_INCREMENT, -> PRIMARY KEY (`id`), -> KEY `id` (`id`) USING HASH -> ) ENGINE=MEMORY DEFAULT CHARSET=latin1; Query OK,...

Find the median of binary search tree, C++

c++,algorithm,vector,time-complexity,binary-search-tree
Once I was interviewed by "One well known company" and the interviewer asked me to find the median of BST. int median(treeNode* root) { } I started to implement the first brute-force solution that I came up with. I fill all the data into a std::vector<int> with inorder traversal (to...

Time Complexity O(V^3) or O(V^2)?

algorithm,time-complexity
I'm new for analyzing the algorithms and the time for them.. This algorithm is posted in http://geeksforgeeks.com and they wrote that the time complexity of the algorithm is O(V^2) which i think that it's O(V^3): int minDistance(int dist[], bool sptSet[]) { // Initialize min value int min = INT_MAX, min_index;...

Time Complexity of a simple piece of Code [closed]

java,algorithm,time-complexity
Here is a simple piece of code. What's it's time complexity? for(int i=0;i<n;i++){ String temp=""; for(int j=i;j<n;j++){ temp+=S.charAt(j); } System.out.println(temp); } N<=5000 The code above is giving me TLE while the next simple code gives me Wrong Answer: for(int i=0;i<n;i++){ String temp =""; for(int j=i;j<n;j++){ } System.out.println(temp); } ...

Complexity classes examples

time-complexity,complexity-theory
I wanted to know if my answers are indeed correct for the following statements: 3(n^3) + 5(n^2) + 25n + 10 = BigOmega(n^3) -> T ->Grows at a rate equals or slower 3(n^3) + 5(n^2) + 25n + 10 = Theta(n^3) -> T -Grows at a rate exactly equals 3(n^3)...

Java TreeMap time complexity - lowerKey

java,time-complexity,treemap
What is the time complexity of the lowerKey() operation in Java implementation of TreeMap ? I think it is log(n) but I can't find it anywhere in the documentation. The complexity of more basic operation is well documented: This implementation provides guaranteed log(n) time cost for the containsKey, get, put...

What is the Time Complexity of finding the max k integers?

python,algorithm,dictionary,big-o,time-complexity
def max_k_sort(k, nums): # sort nums first using timsort # add O(n*log(n)) time complexity sorted_nums = sorted(nums) return sorted_nums[-1*k:len(nums)] def max_k(k, nums): # build initial max number list max_nums = {} # add O(k) time complexity? i = 0 while i < k: max_nums[i] = 0 i += 1 #...

Recurrence relation: iteration solving

algorithm,iteration,time-complexity,recurrence,upperbound
There is a recurrence relation as following: T(n) = 2 T(n-1) + O(1) for n > 1 otherwise, its T(n) = O(1) By iteration , so far I got like, T(n) = 2(2T(n-2) + 1) + 1 --- 1 T(n) = 2(2(2T(n-3) + 1) + 1) + 1 ---- 2...

Is complexity of scala.xml.RuleTransformer really exponential?

xml,scala,time-complexity
This is a follow-up to one of my previous posts. I tried to understand why the RuleTransformer performance is so poor. Now I believe that it is so slow because its complexity is O(2n), where n is the height of the input XML tree. Suppose I need to rename all...

Have I properly sorted these runtimes in order of growth?

math,big-o,time-complexity,asymptotic-complexity
I am doing this small task which I have to arrange asymptotic runtime in ascending order. Here are the runtimes: Here is the order I believe they should go in: log10(n^4), n^3, 2^((log4n)), 2^(100n), e^pi^4096, n! + 12^1000 Is this correct? Or are there any errors? Thanks!...

How much time the fastest supercomputer will take to run this code? [closed]

java,performance,algorithm,data-structures,time-complexity
I have a simple code for finding the nth fibonacci series number. public class Recursion { static int num; public static int fib(int n){ num++; System.out.println(num); if(n<=1){ return n; } else{ return fib(n-2)+fib(n-1); } } public static void main(String...strings){ System.out.println(fib(100)); System.out.println("number of repetitions is "+num); } } I have done...

Why is the cost of a hash lookup O(1) when evaluating the hash function might take more time than that?

hash,hashtable,big-o,time-complexity
A HashMap (or) HashTable is an example of keyed array. Here, the indices are user-defined keys rather than the usual index number. For example, arr["first"]=99 is an example of a hashmap where theb key is first and the value is 99. Since keys are used, a hashing function is required...

Understanding complexity of JavaScript algorithm using object as a hash

javascript,algorithm,time-complexity
I'm trying to come up with an algorithm to solve the following problem. Given an array of ids var ids = [8098272281362432, 7824519999782912]; Find all the matches in an array of items. var people = [ { "id": 8098272281362432, "age": 59, "name": "Douglas Hunter" }, { "id": 625873891885056, "age": 1,...

Finding the complexity of a function

python,max,time-complexity,complexity-theory
I am trying to calculate the time complexity of the next function, max_list11, which finds a maximum of a list recursively: def max11(L,left,right): if left==right: return L[left] return max(L[left], max11(L,left+1,right)) def max_list11(L): return max11(L,0,len(L)-1) From what I found out, the time complexity should be O(n), since what the function does...

How do nested variable types change time complexity?

python,list,dictionary,set,time-complexity
I'm creating a list with nested types like this: nested = [{}, set([]), []] Assume each item in 'nested' has many items in it. For each type of item in 'nested', what operations from Python's Wiki change complexity because the items are nested? For things like add, remove, pop, etc....

Running time complexity

algorithm,math,time-complexity
For functions f(n) : n! , n^2 and n .. If a problem can be solved in 1 second, given that the algorithm to solve the problem takes f(n)microsecond. I know for a fact n! = 9 in one second. but I don't know how this been calculated. Can someone...

Ranking a given list of integers in less than O(n^2)

java,arrays,algorithm,time-complexity
How to assign ranks to elements in a given list of integers? Is there an algorithm for that with time complexity less than O(n^2) ? Input: 2 6 7 3 9 Output: 1 3 4 2 5 ...

How to find out time complexity of mergesort implementation?

algorithm,big-o,time-complexity
We all know that merge sorting algorithm time complexity is "N Log N". But from this below code how to calculate this "N Log N" big O notation step by step ? There are some answer about this question on internet but they are very complicated to understand. Please help...

Represent the time complexity of the following recursive algorithm, T(n), as a recurrence equation:

c++,algorithm,recursion,time-complexity
I am trying to find the time complexity of the following algorithm : int pow_17(int n) { if(n==1) return 17; if(n>1) return(17 * pow_17(n-1); } So far this is what I have : T(n) = c1 + c2 + c3*log17n+1 + c4*17(n-1) I know this is not correct but can...

Is it possible to return multiple items in my methods?

java,return,time-complexity
I have written three methods of different Big-O complexities. Is there a way to return multiple values in my method without affecting the complexity? Thanks in advance! public static double Nsquare(double[] ar){ double max=0, difference=0; double maxelement=0, minelement=0 ; for (int i=0; i<ar.length;++i){ for (int j=0; j<ar.length;++j){ difference=Math.abs(ar[i]-ar[j]); if (difference>max){...