{"id":34018,"date":"2024-11-01T09:23:08","date_gmt":"2024-11-01T09:23:08","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34018"},"modified":"2024-11-01T10:54:17","modified_gmt":"2024-11-01T10:54:17","slug":"c-coding-test-course-understanding-time-complexity-notation","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34018\/","title":{"rendered":"C# Coding Test Course, Understanding Time Complexity Notation"},"content":{"rendered":"<p>Hello! I greet everyone preparing for C# coding tests. Today, we will explore one of the frequently discussed topics in coding tests, which is time complexity, and we will solve an algorithm problem that applies this concept. Time complexity is an important metric for evaluating the efficiency of algorithms and is particularly crucial in coding tests.<\/p>\n<h2>1. What is Time Complexity?<\/h2>\n<p>Time complexity mathematically represents the increase in the time taken by an algorithm to run as the size of the input (n) increases. This helps us examine how efficiently an algorithm operates. By analyzing time complexity, we can look at the worst-case, best-case, and average-case scenarios.<\/p>\n<h2>2. Notations for Time Complexity<\/h2>\n<p>There are several notations to indicate time complexity, but the most commonly used notations are as follows:<\/p>\n<ul>\n<li><strong>Big O Notation (O-notation)<\/strong>: The most widely used notation, representing the upper bound of a function.<\/li>\n<li><strong>Big \u0398 Notation (\u0398-notation)<\/strong>: Represents both the lower and upper bounds of a function at the same time.<\/li>\n<li><strong>Big \u03a9 Notation (\u03a9-notation)<\/strong>: Represents the lower bound of a function.<\/li>\n<\/ul>\n<p>In coding tests, Big O notation is mainly used to express time complexity.<\/p>\n<h2>3. Problem Description<\/h2>\n<p>Now, let&#8217;s solve a specific algorithm problem. The problem is as follows:<\/p>\n<h3>Problem: Sum of Two Numbers<\/h3>\n<p>Given an integer array <code>nums<\/code> and an integer <code>target<\/code>, the problem is to find two numbers in the array such that they add up to <code>target<\/code> and return their indices. Note that the same element cannot be used twice. The result should return the indices in an array.<\/p>\n<p>For example, if <code>nums = [2, 7, 11, 15]<\/code> and <code>target = 9<\/code>, it should return <code>[0, 1]<\/code>.<\/p>\n<h3>4. Problem Solving Process<\/h3>\n<p>There are several approaches to solve this problem, but here we will describe the two most efficient methods: the brute force method and the method using a hash map.<\/p>\n<h4>4.1. Brute Force Method<\/h4>\n<p>The brute force method involves comparing all pairs in the array to check if their sum is equal to <code>target<\/code>. This method is simple but inefficient with a time complexity of O(n^2). Below is an example implementation in C#:<\/p>\n<pre><code>public int[] TwoSum(int[] nums, int target) {\n    for (int i = 0; i &lt; nums.Length; i++) {\n        for (int j = i + 1; j &lt; nums.Length; j++) {\n            if (nums[i] + nums[j] == target) {\n                return new int[] { i, j };\n            }\n        }\n    }\n    return new int[] { -1, -1 }; \/\/ In case not found\n}<\/code><\/pre>\n<p>The code above iterates through all pairs in the array to check if their sum equals <code>target<\/code>. Consequently, it returns the correct indices for the given input.<\/p>\n<h4>4.2. Method Using Hash Map<\/h4>\n<p>The method using a hash map is an efficient approach that can reduce the time complexity to O(n). This method traverses the array once, storing each number and its index in a hash map. Then, it traverses the array again to check if <code>target - nums[i]<\/code> exists in the hash map. Below is an example implementation:<\/p>\n<pre><code>using System.Collections.Generic;\n\npublic int[] TwoSum(int[] nums, int target) {\n    Dictionary<int, int=\"\"> numDict = new Dictionary<int, int=\"\">();\n    for (int i = 0; i &lt; nums.Length; i++) {\n        int complement = target - nums[i];\n        if (numDict.ContainsKey(complement)) {\n            return new int[] { numDict[complement], i };\n        }\n        numDict[nums[i]] = i; \/\/ Save the current number and index\n    }\n    return new int[] { -1, -1 }; \/\/ In case not found\n}<\/int,><\/int,><\/code><\/pre>\n<p>The code above finds the two numbers that add up to <code>target<\/code> while storing each number in the hash map, thereby reducing unnecessary iterations and significantly enhancing the algorithm&#8217;s performance.<\/p>\n<h2>5. Time Complexity Analysis<\/h2>\n<p>In the case of the brute force method, the time complexity is O(n^2). This is due to the time taken to examine all pairs in the array. In contrast, the hash map method has a time complexity of O(n). It traverses the array once and adds each number to the hash map, where the average lookup time for the hash map is O(1).<\/p>\n<p>By comparing the time complexities of the two methods, we can conclude that the hash map method is much more efficient. Considering the efficiency of algorithms is crucial when preparing for coding tests.<\/p>\n<h2>Conclusion<\/h2>\n<p>In this lesson, we explored time complexity through a problem commonly found in C# coding tests and solved it using two different methods. It is essential to consider efficiency when designing algorithms, and choosing a method with excellent performance is important.<\/p>\n<p>In the next lesson, we will cover more algorithms and techniques for coding tests. I wish you all great success in your job search!<\/p>\n<p>Thank you!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Hello! I greet everyone preparing for C# coding tests. Today, we will explore one of the frequently discussed topics in coding tests, which is time complexity, and we will solve an algorithm problem that applies this concept. Time complexity is an important metric for evaluating the efficiency of algorithms and is particularly crucial in coding &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34018\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;C# Coding Test Course, Understanding Time Complexity Notation&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[90],"tags":[],"class_list":["post-34018","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>C# Coding Test Course, Understanding Time Complexity Notation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/34018\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C# Coding Test Course, Understanding Time Complexity Notation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello! I greet everyone preparing for C# coding tests. Today, we will explore one of the frequently discussed topics in coding tests, which is time complexity, and we will solve an algorithm problem that applies this concept. Time complexity is an important metric for evaluating the efficiency of algorithms and is particularly crucial in coding &hellip; \ub354 \ubcf4\uae30 &quot;C# Coding Test Course, Understanding Time Complexity Notation&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34018\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:23:08+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:54:17+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"4\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34018\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34018\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C# Coding Test Course, Understanding Time Complexity Notation\",\"datePublished\":\"2024-11-01T09:23:08+00:00\",\"dateModified\":\"2024-11-01T10:54:17+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34018\/\"},\"wordCount\":620,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C# Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34018\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34018\/\",\"name\":\"C# Coding Test Course, Understanding Time Complexity Notation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:23:08+00:00\",\"dateModified\":\"2024-11-01T10:54:17+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34018\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34018\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34018\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C# Coding Test Course, Understanding Time Complexity Notation\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"C# Coding Test Course, Understanding Time Complexity Notation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/34018\/","og_locale":"ko_KR","og_type":"article","og_title":"C# Coding Test Course, Understanding Time Complexity Notation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello! I greet everyone preparing for C# coding tests. Today, we will explore one of the frequently discussed topics in coding tests, which is time complexity, and we will solve an algorithm problem that applies this concept. Time complexity is an important metric for evaluating the efficiency of algorithms and is particularly crucial in coding &hellip; \ub354 \ubcf4\uae30 \"C# Coding Test Course, Understanding Time Complexity Notation\"","og_url":"https:\/\/atmokpo.com\/w\/34018\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:23:08+00:00","article_modified_time":"2024-11-01T10:54:17+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"4\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34018\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34018\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C# Coding Test Course, Understanding Time Complexity Notation","datePublished":"2024-11-01T09:23:08+00:00","dateModified":"2024-11-01T10:54:17+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34018\/"},"wordCount":620,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C# Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34018\/","url":"https:\/\/atmokpo.com\/w\/34018\/","name":"C# Coding Test Course, Understanding Time Complexity Notation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:23:08+00:00","dateModified":"2024-11-01T10:54:17+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34018\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34018\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34018\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C# Coding Test Course, Understanding Time Complexity Notation"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34018","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34018"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34018\/revisions"}],"predecessor-version":[{"id":34019,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34018\/revisions\/34019"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34018"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34018"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34018"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}