1 vote
516 views

### Computational complexity of generating a random vector

I'm new to the concept of computational complexity and trying to understand the topic in depth. I went through some references mentioned by some old questions, however, I had this question and not ...
• 13
1 vote
144 views

### What exactly is bigO notation? [duplicate]

I've heard of bigO notation but I don't really understand how do I determine it for my code and what exactly does it represent? I heard that there are two: RunTime Memory Complexity How can I learn ...
1 vote
125 views

### Big-O in computer Science [duplicate]

As the title states, I am asking for how the big-O in asymptotic analysis is used in theoretical computer science. It would be helpful if an example would be given.
1 vote
1k views

### Memoized Palindrome Subsequence

I am trying to find the maximum palindrome sub-sequence and after going through some tutorials, I came up with a memoized version.But I am not sure about the runtime.I want to know if the following ...
• 355
141 views

### Understanding time complexity of algorithm to determine if parenthesis are matching

Both these algorithms determine if all the parenthesis in a string are balanced and properly nested. The first algorithm uses "a constant amount of memory, regardless of the length of the string.&...
608 views

### Algorithm Time complexity analysis for algorithm having two different time complexities

I'm implementing an algorithm that analyze several properties on large set of integers, the time complexity is bound to $N$ (set length) and $M$ (bits to represent the numbers). I'm having some ...
• 519
81 views

### Converting a algorithm to a runtime function

I need to find an upper limit for the runtime of $f(n)$. ...
• 143
60 views

### Reccurrence equation and finding suitable algorithm

I'm given the following recurrence equation: \begin{align*} T(1) &= 0\\ T(n) &= T(n/2) + 1 && \text{when $n > 1$ is even}\\ T(n) &= T((n+1)/2) + 1 && \...
• 103
194 views

### How to get an O(n) for a search algorithm [duplicate]

Given an two sorted arrays X and Y, both of size n. Determine if there is an element x of X and an element y of Y such that x = 3y. The algorithm needs to run in linear time in the worst case. At the ...
• 129
1 vote
66 views

### Big-Oh of algorithm

I found an algorithm which sorts the digits of a number to its smallest form. IE 54321 ==> 12345. The algorithm looks like: ...
70 views

### Time complexity of this for-loop

I know, the inner loop here is O(log n). But, I get confused by the multiplication in the outer loop part. ...
• 125
644 views

### Implement Immediate Smaller Element problem using Stack

Immediate Smaller Element Problem: Given an integer array arr of size $n$. For each element in the array, check whether the right adjacent element (on the next ...
• 101
19 views

### Big o notation for the algo [duplicate]

Asked this at programmers Stack Exchange, was recommend to ask here : What would be the big o for the algo: for (i=0; i < n*n; i++) for(j=0; j<i*i; j++) ...
• 1
31 views

### Am I doing this correctly? Recurrence Relations [duplicate]

The function is this: ...