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...

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...

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...

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!...

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...

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);...

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)...

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 <=...

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.

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...

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...

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...

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...

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...

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,...

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?...

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 >...

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 +...

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))...

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....

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...

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:...

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...

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);...

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...

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...

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...

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...

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 < =...

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...

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......

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...

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....

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)...

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"...

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...

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...

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 ...

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) #...

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++ )...

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 =...

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...

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...

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...

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,...

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++) {...

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?...

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...

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;...

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) ?...

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); } ...

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...

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...

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...

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){...

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++; } ...

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 <...

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 =...

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...

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 ==...

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...

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?

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...

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....

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 #...

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...

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...

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...

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,...

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...

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,...

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...

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...

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...

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 =...

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? ...

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 +...

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...

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...

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...

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?

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...

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...

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...

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...

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...

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...

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...

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...

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...

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

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...

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...

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 ...

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...

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;...

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...

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...

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....

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...