So I am given a function like 65536 n^{2} + 128 n log_{2}n

and the only way that this would be O(n^{2} log_{2}n) is if

C = 65664, n0 = 2 for all n ≥ 2 since

C1 = 65536 n1 = 2 when 65536 ≤ C1*n^{2} and

C2 = 128 n2 = 1 when 128 ≤ C2*n

but the number I've chosen for the constant seems a bit to high, is there a way to check this?

Answer:

O(65536 n^{2} + 128 n log_{2}n) is the same as O(n^{2} + n log_{2}n) since you can ignore multiplicative constants. O(n^{2} + n log_{2}n) is equal to **O(n ^{2})** since n

Also, by the way, the base of logarithms doesn't matter in Big-O analysis. All logarithms grow at the same rate. After all, log_{2}n = log n / log 2, and multiplicative constants can be factored out. You can simply say log n instead of log_{2}n.

**Caveat:** Technically, it is actually a true statement to say that 65536 n^{2} + 128 n log_{2}n ∈ O(n^{2} log_{2}n) because Big-O gives *an* upper bound, but not a strict one. O(n^{2}) is a *lower* upper bound, if that makes sense.

That said, you should not have come up with O(n^{2} log_{2}n). That was merely the result of accidentally turning an addition into a multiplication. As a rule of thumb, if you have multiple things added together inside a Big-O formula, you just have to figure out which one of them grows the fastest and then discard the others.

performance,algorithm,big-o,bigdata,asymptotic-complexity

I have an array with, for example, 1000000000000 of elements (integers). What is the best approach to pick, for example, only 3 random and unique elements from this array? Elements must be unique in whole array, not in list of N (3 in my example) elements. I read about Reservoir...

algorithm,big-o

I have the following: n! nlogn 2 ^ n sqrt3(n) = n^1/3 n ^ 3 We know that in order to compare two functions we need lim n->infinity f(n) / g(n) But we also know that exponential > polynomial > polylogarithmic. We also know from stirling that n! = o(n^n)...

algorithm,linked-list,computer-science

There is a data structure providing iterators with the following interface: struct iterator { T value(); void next(); bool isValid(); } How would you design an algorithm which at the end of the loop returns some value from the list with equal probability for each element? The list can be...

c++,c,arrays,linked-list,big-o

I've made a game by using 9 linked Lists and the other 1 linked lists gets all the address of the other 9 linked lists. Therefore, something like a 2 dimensional array by using linked list. I'm trying to calculate Big-O that my data structure fits and is better than...

computer-science,computer-architecture

A cache memory with 4 KiB, each block is 16 words, there are 64 lines in the cache. Tag = 18 Index = 6 Block offset = 4 Byte Offset = 2 I want to know for block number 448 what is the first address in the block and what...

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

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

java,big-o

public static void main(String[] args) { int count = 0; int n = 20; for (int i = 0; i < n; i++) { for (int j = i; j > 0; j--) { count++; } } System.out.println(count); } Above is the code of a simple nested for loop...

c++,c,algorithm,big-o

The generic algorithm to deduce if a string contains all unique characters (and that does not use any other data structures) says to go through the string, iterating each letter against the entire string searching for a match. This approach is O(n^2). The approach below (written in C) uses an...

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

python-2.7,matplotlib,computer-science,floating-point-conversion

I am finding errors with the last line of the for loop where I am trying to update the curve value to a list containing the curve value iterations. I get errors like "can only concatenate tuple (not "float) to tuple" and "tuple object has no attribute 'append'". Does anyone...

algorithm,big-o,complexity-theory,exponential

According to Wikipedia article on Exponential growth E.g. if a slow processor can solve problems of size x in time t, then a processor twice as fast could only solve problems of size x+constant in the same time t. My question is, how do we calculate the constant value that...

java,arrays,big-o

I'm looking for the greatest difference between 2 doubles in a list, I have done it this way in NlogN time, is there a way to do it in linear time? thanks! public static double NlogN(double[] ar){ Arrays.sort(ar); double max=ar[ar.length-1]; double min=ar[0]; double difference=max-min; return difference; } ...

algorithm,recursion,big-o,complexity-theory,recurrence

The question comes from Introduction to Algorithms 3rd Edition, P63, Problem 3-6, where it's introduced as Iterated functions. I rewrite it as follows: int T(int n){ for(int count = 0; n > 2 ; ++count) { n = n/log₂(n); } return count; } Then give as tight a bound as...

algorithm,sorting,big-o,computer-science,asymptotic-complexity

I know that measuring asymptotic complexity can be based on any resources you have, whether it's time, memory usage, number of comparisons, etc. But when it comes to sorting something, I realize we normally associate the asymptotic notation with the basic operations like number of swaps/steps or number of comparisons....

javascript,computer-science

In JavaScript, there is the concept of the execution pathway beginning at a certain point (such as an event handler), with the control being relinquished back to the browser at some point. Is there a proper name for this process? Originally I thought you could refer to this as the...

python,algorithm,performance,big-o

So this is an algorithms question I was working out on HackerRank. It passes all the test cases except one because it times out. I tried making a couple of improvements but it still keeps timing out. I want to understand how you can look at your own code and...

ruby,boolean,computer-science

Why is nil considered a boolean or represented as a boolean value in the boolean tutorial for ruby? By definition, a boolean in computer science is a: data type, having two values (usually denoted true and false), intended to represent the truth values of logic and Boolean algebra. ...

graph,big-o,notation

I'm going through some programming interview question books, and I've seen reference to "O(|A|)" time complexity. I've never seen this notation with the absolute value given. Some research led me to Big O Cheatsheet that references this notation under the graphs section. The problem I'm researching is about partitioning an...

algorithm,graph,tree,runtime,big-o

I have a possible solution for the following question, but not sure if correct: Assume we have already found a minimum spanning tree T for a weighted, undirected graph G = (V,E). We would like to be able to efficiently update T should G be altered slightly. An edge is...

c#,performance,if-statement,big-o,ternary

I did the due-diligence to see if this has been asked before and didn't find anything identical but close, so here goes. Say I have a chain of if-else-if statements. foreach (value in valueList) if (value == 120) { w = true; } else if (value == 140) { x...

algorithm,graph,tree,runtime,big-o

I am having trouble with the following question: Assume we have already found a minimum spanning tree T for a weighted, undirected graph G = (V,E). We would like to be able to efficiently update T should G be altered slightly. An edge is removed from G to produce a...

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

java,computer-science

I am facing following problem: I have a board of size MxN squares. What is the best way to make it in java so that when there are coordinates given which are out of bounds (or with negative values), it will return square from the other side of the board?...

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

c,function,for-loop,computer-science

I'm trying to re-create brickbreaker using C and the Stanford Portable Library (SPL). The goal of my initBricks function is to add 5 ROWS of bricks with 10 COLUMNS in each row (50 bricks total). When I run this code my window only has 1 ROW of 10 bricks. For...

algorithm,big-o

I was doing some reading on logarithms and the rate of growth of the running time of algorithms. I have, however, a problem understanding the Big-Ω (Big-Omega) notation. I know that we use it for 'asymptotic lower bounds', and that we can express the idea that an algorithm takes at...

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

big-o,computer-science

So I am given a function like 65536 n2 + 128 n log2n and the only way that this would be O(n2 log2n) is if C = 65664, n0 = 2 for all n ≥ 2 since C1 = 65536 n1 = 2 when 65536 ≤ C1*n2 and C2 =...

java,computer-science,keylistener,keyevent

I have recently started learning java.I want to make a game like https://sites.google.com/site/millseagles/home/Games/multiplayer/tron I have made it in c++ once using a simple graphics lib. I have the graphics part down i plan to use small images and use http://horstmann.com/sjsu/graphics/ this basic graphics lib.I can't figure out keyboard input i...

algorithm,big-o

With m and n being the two dimensions of a 2D matrix, which search algorithms with givens Big-O are considered faster: log(m*n) or (m+n) or log(m)*log(n)? ...

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

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

algorithm,big-o

Just reading this book for fun, this isn't homework. However I am already confused on the first main assignment: 1-1 Comparison of running times For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t,...

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

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

arrays,algorithm,sum,big-o,subset

Given an array {1,3,5,7}, its subparts are defined as {1357,135,137,157,357,13,15,17,35,37,57,1,3,5,7}. I have to find the sum of all these numbers in the new array. In this case sum comes out to be 2333. Please help me find a solution in O(n). My O(n^2) solution times out. link to the problem...

algorithm,matlab,time,big-o,nested-loops

I have a code that generates all of the possible combinations of 4 integers between 0 and 36. This will be 37^4 numbers = 1874161. My code is written in MATLAB: i=0; for a = 0:36 for b= 0:36 for c = 0:36 for d = 0:36 i=i+1; combination(i,:) =...

c,programming-languages,computer-science,systems-programming,inventions

I'm novice programmer, learning C. Something that's always confused me is how do people create new programming languages? Sub/related questions: What language do they write it in? Does the language have to be one that in between a high level language and machine code? What are the stages/elements of creating...

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

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

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

c++,c,arrays,big-o

If i have N x N 2 dimensional array and the name is a. int a[N][N]; When i Insert any value in any array, for example, a[N-1][N-1]=1, how much time does it take? O(N^2) or O(1)?...

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

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

c,for-loop,big-o

I know how to find Big O for "for loops" and nested "for loops", but what happens when we have two for loops, not nested but two separate for loops in the same function.

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

algorithm,heap,computer-science,fibonacci-heap

I am studying Fibonacci heap alone, and I came across a question. I know any nodes can be inserted into Fibonacci heap, but what if the rank(or value, or key) of that new node is equal to the sibling node? 1) For example, (1) <-minimum root / \ (3) (5)...